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