求子数组的最大累加和

题目：

image.png

思路：

首先要知道，子数组在原数组中的位置必须是连续的！
最简单的方法：设置两个变量，一个变量cur，记录当前累加到的位置，如果累加到一个位置，当前位置的累加和小于零那么就把cur置为0，从下一个位置继续算累加和；另一个变量max，记录每一步累加的最大值，即从0位置开始，加一个1位置，cur记录累加值，如果cur小于零，cur置为0，max页记录累加值，只不过max记录的一直是最大值，无论正负，max=Math.max(max,cur)

这种思路的可行性：分三种情况
1.原数组全部是负数比如{-3,-2,-7,-1}
当i=0 cur=-3,因为cur<0，cur=0，max=-3
当i=-2是 cur=-2，因为cur<0 cur=0，因为-2>-3所以max=-2
依次进行下去得出最大累加和就是-1
2.既有整数又有负数比如{1,-2,3-1}
当i=0 cur=1 max = 1
当i=1 cur=-1 因为-1<0 所以cur=0 max=-1
当 i=2 时 cur=3 max=3
等等 所以最后结果max=3
3.全是整数，即把每个数都加上肯定最大
解释：为什么这样做对，假设我现在知道了（i,j）位置的累加和最大，那么在（i,k） i<k<j，内的累加和必不可能小于零，因为如果小于零（i,j）的累加和就不可能最大，同理，i左边位置的累加和肯定<=0所以，通过cur记录位置并且当cur<0，从下一个位置重新计数，而max记录最大值，这样不会落下任何一种情况，这样求出来的答案时子数组长度最大的最大累加和

代码：

    public static int maxSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i != arr.length; i++) {
            cur += arr[i];
            max = Math.max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }