目录

最大子序和

lienhui68 收录于技术

2020-06-12 约 328 字预计阅读 1 分钟次阅读

目录

题目

给定一个整数数组 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;
    }