锐客网

  1. 首页 > it技术 > >

算法复习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; imax) 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[i]之间不一定连续，也就是说直接相加可能会跳过中间的一些值。
    【算法复习3——连续子数组的最大和】示例：数组[1,-5,5] 错误方案求出的最大和是6，实际结果应该是5

    推荐阅读


    上一篇：谷歌性能指标优化

    下一篇：算法复习4——求一组数的全排列