剑指Offer：连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值 。要求时间结复杂度为 O(n)。

例如输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为｛3,10 -4,7, 2｝ ，因此输出为该子数组的和18。

解法一：举例分析数组的规律

      我们试着从头到尾逐个累加示例数组中的每个数字，保存到sum（初始化和为 0）中。第 一步加上第一个数字 1，此时和为1，接下来第二步加上数字-2，和就变成 了-1。第三步刷上数字 3。我们注意到由于此前累计的和是-1，小于 0，那 如果用-1加上 3，得到的和是 2，比3本身还小。也就是说从第一个数字开始的子数组的和会小于从第三个数字开始的子数组的和。因此我们不用考虑从第一个数字开始的子数组，之前累计的和也被抛弃。

      我们从第三个数字重新开始累加，此时得到的和是 3。接下来第四步加 10，得到和为 13。第五步加上-4，和为 9。我们发现由于-4 是一个负数， 因此累加-4 之后得到的和比原来的和还要小。因此我们要把之前得到的和 13 保存下来，它有可能是最大的子数组的和。第六步加上数字.7，加 7 的,结果是 16，此时和比之前最大的和 13 还要大，把最大的子数组的和由 13 更新为 16。第七步加上 2，累加得到的和为 18，同时我们也要更新最大子数组的和。第八步加上最后一个数字-5，由于得到的和为 13，小于此前最大的和 18，因此最终最大的子数组的和为 18，对应的子数组是｛3, 10,-4, 7,2｝。

实现代码：

private static int FindGreatestSumOfSubArray(int[] array){
    if(array==null||array.length==0){
        throw new RuntimeException("array==null||array.length==0");
    }
    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    for(int i=0;i<array.length;i++){
        if(sum<=0){
            sum = array[i];
        }else{
            sum += array[i];
        }
        if(sum>maxSum){//当前的sum大于之前保存的maxSum，更新maxSum
            maxSum = sum;
        }
    }
    return maxSum;
}

解法二：动态规划法

      如果用函数 f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求max[f(i)] ，其中 o <=i<arr.length。我们可用如下边归公式求 f(i):

      这个公式的意义：当以第 i-1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第 i个数累加，得到的结果比第 i个数字本身还要小，所以这种情况下以第 i个数字结尾的子数组就是第 i个数字本身。如果以第 i-1 个数字结尾的子数组中所有数字的和大于 0, 与第 i个数字累加就得到以第 i个数字结尾的子数组中所有数字的和。

实现代码：

private static int FindGreatestSumOfSubArray(int[] array){
    if(array==null||array.length==0){
        throw new RuntimeException("array==null||array.length==0");
    }
    int sum=0;
    int maxSum = Integer.MIN_VALUE;
    for(int i=0;i<array.length;i++){
        sum = f(array,i);
        if(sum>maxSum){
            maxSum = sum;
        }
    }
    return maxSum;
}

private static int f(int[] array,int i){
    if(i==0||f(array,i-1)<=0){
        return array[i];
    }
    if(i!=0&&f(array,i-1)>0){
        return f(array,i-1)+array[i];
    }
    return 0;
}