关于java:算法复习3连续子数组的最大和

应用滑动窗口法：

重点： 须要存储以后滑动窗口的和，如果 <=0，就不须要在它的根底上加上以后值

public int FindGreatestSumOfSubArray(int[] array) {
        // 滑动窗口法：if(array==null || array.length==0)
            return -1;
        int max=Integer.MIN_VALUE;// 存储最大值, 初始化为极小值
        int tempSum=0; // 以后滑动窗口的和
        for(int i=0;i<array.length;i++){if(tempSum<=0){// 以后滑动窗口的和 <=0，则不须要在它的根底上加第 i 项
                tempSum=array[i];
            }
            else{tempSum+=array[i];
            }
            if(tempSum>max)
                max=tempSum;
        }
        return max;
}

易错点：（下面的 tempSum 就是此处的 preSum），preSum 的更新基于最大值，这种思路是谬误的！！！

public int FindGreatestSumOfSubArray(int[] array) {
    // 动静规划法
    if(array==null || array.length==0)
            return -1;
    int preSum=0;// 前一次的后果
    int realSum=Integer.MIN_VALUE;// 后一次的后果
    for(int i=0;i<array.length;i++){preSum = Math.max(array[i], realSum + array[i]);
        realSum = Math.max(realSum, preSum);
    }
    return realSum;
}

起因剖析： 最大和的更新基于上次的最大和，然而上次的最大和与 array[i] 之间不肯定间断，也就是说间接相加可能会跳过两头的一些值。

示例： 数组 [1,-5,5] 谬误计划求出的最大和是 6，理论后果应该是 5