求客位java高手指点一二。。

Question

一次面试中遇到这样一道题：每个int型的数组都有n个字集。如{1,-1,3}的子数组有{1},{3},{-1},{1,-1},{1,3},{-1,3},{1,-1,3}这些子数组中和最大的是4,要求写一方法求出一个int 型数组的所有子集中最大的和；
    当时没答出来，在网上google了一下，有很各种各样的答案，自己也写了一个（试了一下还可以），就是不清楚它的不足之处，请各位高手给于指正：
public static int intSum(int[] m){
int sum=0;
ArrayList list=new ArrayList();
//把所有的负数加入到一个list中草药，如果该数组全是负数，则m.length==list.size()。只找到最大的那个就可以了。
for(int i=0;i<m.length;i++){
if(m[i]<0){
list.add(m[i]);
}
}
if(list.size()==m.length){
for (int i = 1; i < m.length; i++) {
sum=m[0];
if(m[i]>sum){
sum=m[i];
}
}
}else{
for (int i = 0; i < m.length; i++) {
if(m[i]>0){
sum+=m[i];
}
}
}
return sum;
}

Answer 1

你程序中的sum=m[0]; 应该放到for的外面。用一个for循环就应该能搞定。sum=0;max=Integer.MIN_VALUE;
for(int i=0;i<a.length;i++){
   if(a[i]>0){
       sum+=a[i];
   }else if(a[i]>max){
      max=a[i];
   }
}
if(sum==0&&max<0) sum=max;sum就是你求的数。

Answer 2

LZ，你的意思是不是求和最大的子集啊
那样的话只要从原数组中找到非负数，存入ArrayList中，这样不就可以了吗

Answer 3

我和你的思路是一样的。但由于只需求出和就可以了，所以就直接求值了。因为考虑到数组中元素全为负，所以把所有的负数添加到ArrayList中然后判断是size()是否和原数组的长度相等。