关于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