前缀和

考虑一般情况：

设前缀和数组为：s

以下分析过程下标均为1 ~ n，但是代码中是0 ~ n-1，前缀和一般来说以1 ~ n 进行分析比较简单。

取1~i的连续子数组的最大和res：那么res = s[i] - s[j] 或者 res = s[i] j的取值范围为[1,i - 1];
所以我们维护一个变量记录最小值即可。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] arr) {
        int n = arr.length;
        int mi = 100000000;
        int res = -100000000;
        for(int i = 1;i < n;i++){
            arr[i] += arr[i - 1];
        }
        for(int i = 0;i < n;i++){
            res = Math.max(res,arr[i]);
            res = Math.max(res,arr[i] - mi);
            mi = Math.min(mi,arr[i]);
        }
        return res;
    }
}