剑指offer面试题42(java版):连续子数组的最大和

welcome to my blog

剑指offer面试题42(java版):连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

思路

• 用sum记录连续n项的和, 当sum小于等于0时, 将sum重置为第n+1项的值, 继续向下遍历
• 核心: 当sum小于等于0时要重置sum; 等于0是为了处理起始项, 最开始sum=0, 将起始项array[0]赋值给sum

        /*
        动态规划:
        令f(i)表示索引从0到i这段区间中的和的最大值, 对应代码中的currMax
        递推关系
            f(i) = f(i-1) + array[i]  if f(i-1)>0
            f(i) = array[i]  if f(i-1)<=0 or i==0
        */
        

动态规划(循环版1)

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        /*
        连续求了n个数的和, 如果这n个数的和小于等于0, 那么把第n+1个数赋给和. 因为连续的n+1数的和小于等于第n+1个数
        如果这n+1个数的和大于0, 那么把第n+1个数加到和上,直到遍历完数组或者和小于等于零才会重置和
        注意一点: 前面说"如果这n个数的和小于等于0", 为什么不限制为小于0,而是限制为小于等于0, 这是为了处理array[0]用的, sum初始值是0, 所以需要把array[0]赋值给sum
        注意一点: 这个思路没有讨论array[i]值的大小, 只通过观察sum的值进行状态的改变
        注意一点: sum是array[i]之前的连续n项和, 也就是根据sum的大小, 决定array[i]是加到sum上还是直接赋值给sum
        注意一点: 需要设置一个变量记录当前的最大值, 因为sum并不代表当前的最大值, 只是尽力维持连续n项和大于0
        */
        int sum = 0, currMax=Integer.MIN_VALUE;
        for(int i=0; i<array.length; i++){
            if(sum <= 0)
                sum = array[i];
            else //sum>0
                sum += array[i];
            if(sum > currMax)
                currMax = sum;
        }
        return currMax;
    }
}

动态规划(循环版2)

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        /*
        动态规划:
        令f(i)表示索引从0到i这段区间中的和的最大值
        递推关系
            f(i) = f(i-1) + array[i]  if f(i-1)>0
            f(i) = array[i]  if f(i-1)<=0 or i==0
        */
        int sum=0, max=Integer.MIN_VALUE;
        for(int i=0; i<array.length; i++){
            sum = Math.max(sum+array[i], array[i]); // 加sum与不加sum, 体现了动态规划的思想
            max = Math.max(sum, max);
        }
        return max;
    }
}

动态规划(递归版)

• 需要控制index, sum, max
• 循环版只用控制sum,max
• 递归可能会产生大量重复子问题,导致时间效率和空间效率都不高
• 注意在哪里返回
• 注意递归中sum和max的处理, max稍微复杂一点
  • currMax=Core(array, index+1, sum+array[index], sum+array[index]>max?sum+array[index]:max);
  • currMax=Core(array, index+1, array[index], array[index]>max?array[index]:max);

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        /*
        动态规划:
        令f(i)表示索引从0到i这段区间中的和的最大值
        递推关系
            f(i) = f(i-1) + array[i]  if f(i-1)>0
            f(i) = array[i]  if f(i-1)<=0 or i==0
        */
        return Core(array, 0, 0, Integer.MIN_VALUE);
    }
    public int Core(int[] array, int index, int sum, int max){
        //recursion finish
        if(index==array.length)
            return max;
        //
        int currMax;
        if(index==0){
            currMax=Core(array, index+1, array[index], array[index]); //注意区分index++和index+1, index++会改变index的值, index+1不会改变index的值
        }
        else{ //index>0
            if(sum>0)
                currMax=Core(array, index+1, sum+array[index], sum+array[index]>max?sum+array[index]:max);
            else // sum<=0
                currMax=Core(array, index+1, array[index], array[index]>max?array[index]:max);
        }
        return currMax;
    }
}