编程珠玑的求最大子集的题

编程珠玑第二版 第8章  给一个数组 求该数组的最大子集和

 

其中最好的算法是扫描算法 O(n)

用java代码实现如下

public class MaxSubArray {
    public static void main(String[] args) {
        int array[] = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 };
//        int array[] = { -31, -41, -111,-12};
        int maxsofar = 0;
        int maxendinghere = 0;
        for (int i = 0; i < array.length; i++) {
            maxendinghere = (maxendinghere + array[i] > 0 ) ? (maxendinghere + array[i]) : 0;
            maxsofar = maxsofar > maxendinghere ? maxsofar : maxendinghere;
            System.out.println(i+":   "+maxendinghere + "   " + maxsofar);
        }
        System.out.println("final:  "+maxendinghere + "   " + maxsofar);
    }
}

 

这其中有几个问题

1. 假如数组里面全是负数， 这题答案就是不对的

2. 这个问题可以说是上一题的root cause,  为什么用0做判断的准则， 我试过把0换成10, 也可以得出结果

 

 

 

 

 

 

评论

2 楼 lich0079 2011-06-02  

不是 是求最大的子集和

1 楼 mirguest 2011-06-02  

我记得书上是不是说总的求和为零？