描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

示例：

  • 输入：[1,-2,3,10,-4,7,2,-5]
  • 输出：18

思路1：暴力破解

计算所有子数组的和，保存最大值（会超时）

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int ret = Integer.MIN_VALUE;
        for(int i = 0; i < array.length; i++) {
            int sum = array[i];
            ret = Math.max(ret, sum);
            for(int j = i + 1; j < array.length; j++) {
                sum += array[j];
                ret = Math.max(ret, sum);
            }
        }
        return ret;
    }
}

思路2：动态规划

dp[i]表示以array[i]结尾的所有子数组的最大和。相当于把前i-1个数合并为1个数

  1. 当dp[i-1]大于0时，加上当前的数，值必然会增大
  2. 当dp[i-1]小于0时，加上当前的数，值返回会减小，因此可以直接去除

可得状态转移方程：

  1. dp[i] = Math.max(dp[i - 1] + array[i], array[i])
  2. dp[i] = dp[i - 1] > 0 ? dp[i - 1] + array[i] : array[i]

示例：

  1. [1,-2,3,10,-4,7,2,-5]
  2. [-1,3,10,-4,7,2,-5]
  3. [3,10,-4,7,2,-5]：舍弃-1，从3开始，不断去除负数边界
  4. [13,-4,7,2,-5]
  5. [9,7,2,-5]
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        int ret = array[0];
        dp[0] = array[0];
        for(int i = 1; i < array.length; i++) {
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            ret = Math.max(dp[i], ret);
        }
        return ret;
    }
}

优化：由于只会用到上一个dp，因此可以只用一个变量保存

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int ret = array[0];
        int sum = array[0];
        for(int i = 1; i < array.length; i++) {
            sum = sum > 0 ? sum + array[i] : array[i];
            ret = Math.max(sum, ret);
        }
        return ret;
    }
}

思路3：贪心算法

贪心算法：保存局部最优解，并扩展到全局

类似思路2：当sum<0时，再加上当前值，结果必然减小，因此可以去除。

  1. 每次扩大窗口，不断加入下一个数
  2. 当窗口内的元素和小于0时，舍弃窗口
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int ret = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < array.length; i++) {
            sum += array[i];
            if(sum > ret) {
                ret = sum;
            }
            if(sum < 0) {
                sum = 0;
            }
        }
        return ret;
    }
}