目录

最大子序和

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

分析

看到“最”字很容易联想到dp, 下面我们试着去推导出递推公式。 假设数组为s,s[i]表示第i号元素,f[i]表示到第i号元素的具有最大和的连续子数组的最大和

$\begin{aligned} & f[0] = -2 \
& f[1] = 1 + max(f[0], 0) = 1 \
& f[2] = -3 + max(f[1], 0) = -2 \
& f[3] = 4 + max(f[2], 0) = 4 \
& … \end{aligned}$

因为要求连续f[i]如果最大,f[i-1]必须是正数才行,所以可以推导出递推公式 $f[i] = max(f[i-1], 0) + s[i], i > 0$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    /**
     * 求最大子序和
     */
    public static int getMaxSubSeqSum(int[] s) {
        int[] f = new int[s.length]; // 最大和
        f[0] = s[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < s.length; i++) {
            // f[i] = max(f[i-1] + s[i], 0) + s[i], i > 0
            f[i] = Math.max(f[i - 1], 0) + s[i];
            max = Math.max(max, f[i]);
        }
        return max;
    }