labuladong 的算法小抄 > 第二章、手把手刷动态规划 > 子序列类型问题 > 动态规划设计：最大子数组

动态规划设计：最大子数组

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
53. Maximum Subarray	53. 最大子数组和	🟠
-	剑指 Offer 42. 连续子数组的最大和	🟢

———–

力扣第 53 题「最大子序和」问题和前文讲过的经典动态规划：最长递增子序列的套路非常相似，代表着一类比较特殊的动态规划问题的思路，题目如下：

给你输入一个整数数组 nums，请你找在其中找一个和最大的子数组，返回这个子数组的和。函数签名如下：

int maxSubArray(int[] nums);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int maxSubArray(vector<int>& nums);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def maxSubArray(nums: List[int]) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func maxSubArray(nums []int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var maxSubArray = function(nums) {}

比如说输入 nums = [-3,1,3,-1,2,-4,2]，算法返回 5，因为最大子数组 [1,3,-1,2] 的和为 5。

其实第一次看到这道题，我首先想到的是滑动窗口算法，因为我们前文说过嘛，滑动窗口算法就是专门处理子串/子数组问题的，这里不就是子数组问题么？

前文滑动窗口算法框架详解中讲过，想用滑动窗口算法，先问自己几个问题：

1、什么时候应该扩大窗口？

2、什么时候应该缩小窗口？

3、什么时候更新答案？

我之前认为这题用不了滑动窗口算法，因为我认为 nums 中包含负数，所以无法确定什么时候扩大和缩小窗口。但经读者评论的启发，发现这道题确实是可以用滑动窗口技巧解决的。

我们可以在窗口内元素之和大于等于 0 时扩大窗口，在窗口内元素之和小于 0 时缩小窗口，在每次移动窗口时更新答案。先直接看解法代码，待会儿再解释：

int maxSubArray(int[] nums) {
    int left = 0, right = 0;
    int windowSum = 0, maxSum = Integer.MIN_VALUE;
    while(right < nums.length){
        // 扩大窗口并更新窗口内的元素和
        windowSum += nums[right];
        right++;

        // 更新答案
        maxSum = windowSum > maxSum ? windowSum : maxSum;

        // 判断窗口是否要收缩
        while(windowSum < 0) {
            // 缩小窗口并更新窗口内的元素和
            windowSum -=  nums[left];
            left++;
        }
    }
    return maxSum;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int maxSubArray(vector<int>& nums) {
    int left = 0, right = 0;
    int windowSum = 0, maxSum = INT_MIN;
    while(right < nums.size()){
        // 扩大窗口并更新窗口内的元素和
        windowSum += nums[right];
        right++;

        // 更新答案
        maxSum = windowSum > maxSum ? windowSum : maxSum;

        // 判断窗口是否要收缩
        while(windowSum < 0) {
            // 缩小窗口并更新窗口内的元素和
            windowSum -=  nums[left];
            left++;
        }
    }
    return maxSum;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def maxSubArray(nums: List[int]) -> int:
    left, right = 0, 0
    windowSum, maxSum = 0, float('-inf')
    while right < len(nums):
        # 扩大窗口并更新窗口内的元素和
        windowSum += nums[right]
        right += 1

        # 更新答案
        maxSum = max(windowSum, maxSum)

        # 判断窗口是否要收缩
        while windowSum < 0:
            # 缩小窗口并更新窗口内的元素和
            windowSum -= nums[left]
            left += 1
    return maxSum

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func maxSubArray(nums []int) int {
    left, right := 0, 0
    windowSum, maxSum := 0, -1<<31
    for right < len(nums) {
        // 扩大窗口并更新窗口内的元素和
        windowSum += nums[right]
        right++

        // 更新答案
        if windowSum > maxSum {
            maxSum = windowSum
        }

        // 判断窗口是否要收缩
        for windowSum < 0 {
            // 缩小窗口并更新窗口内的元素和
            windowSum -= nums[left]
            left++
        }
    }
    return maxSum
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var maxSubArray = function(nums) {
    let left = 0, right = 0;
    let windowSum = 0, maxSum = Number.MIN_SAFE_INTEGER;
    while(right < nums.length) {
        // 扩大窗口并更新窗口内的元素和
        windowSum += nums[right];
        right++;

        // 更新答案
        maxSum = windowSum > maxSum ? windowSum : maxSum;

        // 判断窗口是否要收缩
        while(windowSum < 0) {
            // 缩小窗口并更新窗口内的元素和
            windowSum -= nums[left];
            left++;
        }
    }
    return maxSum;
};

结合前文滑动窗口算法框架详解给出的滑动窗口代码框架，这段代码的结构应该很清晰，我主要解释一下为什么这个逻辑是正确的。

首先讨论一种特殊情况，就是 nums 中全是负数的时候，此时算法是可以得到正确答案的。

接下来讨论一般情况，nums 中有正有负，这种情况下元素和最大的那个子数组一定是以正数开头的（以负数开头的话，把这个负数去掉，就可以得到和更大的子数组了，与假设相矛盾）。那么此时我们需要穷举所有以正数开头的子数组，计算他们的元素和，找到元素和最大的那个子数组。

说到这里，解法代码的逻辑应该就清晰了。算法只有在窗口元素和大于 0 时才会不断扩大窗口，并且在扩大窗口时更新答案，这其实就是在穷举所有正数开头的子数组，寻找子数组和最大的那个，所以这段代码能够得到正确的结果。

动态规划思路

解决这个问题还可以用动态规划技巧解决，但是 dp 数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义 dp 数组：

nums[0..i] 中的「最大的子数组和」为 dp[i]。

如果这样定义的话，整个 nums 数组的「最大子数组和」就是 dp[n-1]。如何找状态转移方程呢？按照数学归纳法，假设我们知道了 dp[i-1]，如何推导出 dp[i] 呢？

如下图，按照我们刚才对 dp 数组的定义，dp[i] = 5 ，也就是等于 nums[0..i] 中的最大子数组和：

那么在上图这种情况中，利用数学归纳法，你能用 dp[i] 推出 dp[i+1] 吗？

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。

所以说我们这样定义 dp 数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义 dp 数组的含义：

以 nums[i] 为结尾的「最大子数组和」为 dp[i]。

这种定义之下，想得到整个 nums 数组的「最大子数组和」，不能直接返回 dp[n-1]，而需要遍历整个 dp 数组：

int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int res = INT_MIN;
for (int i = 0; i < n; i++) {
    res = max(res, dp[i]);
}
return res;

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

res = float('-inf')
for i in range(n):
    res = max(res, dp[i])
return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

res := math.MinInt32
for i := 0; i < n; i++ {
    res = max(res, dp[i])
}
return res

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var res = Number.MIN_VALUE;
for (var i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;

依然使用数学归纳法来找状态转移关系：假设我们已经算出了 dp[i-1]，如何推导出 dp[i] 呢？

可以做到，dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：

// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 要么自成一派，要么和前面的子数组合并
dp[i] = max(nums[i], nums[i] + dp[i - 1]);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 要么自成一派，要么和前面的子数组合并
dp[i] = max(nums[i], nums[i] + dp[i - 1])

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 要么自成一派，要么和前面的子数组合并
dp[i] = max(nums[i], nums[i]+dp[i-1])

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 要么自成一派，要么和前面的子数组合并
var dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

综上，我们已经写出了状态转移方程，就可以直接写出解法了：

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    vector<int> dp(n);
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    int res = INT_MIN;
    for (int i = 0; i < n; i++) {
        res = max(res, dp[i]);
    }
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def maxSubArray(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    # 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    dp = [0] * n
    # base case
    # 第一个元素前面没有子数组
    dp[0] = nums[0]
    # 状态转移方程
    for i in range(1, n):
        dp[i] = max(nums[i], nums[i] + dp[i - 1])
    # 得到 nums 的最大子数组
    res = float('-inf')
    for i in range(n):
        res = max(res, dp[i])
    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func maxSubArray(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    dp := make([]int, n)
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0]
    // 状态转移方程
    for i := 1; i < n; i++ {
        dp[i] = max(nums[i], nums[i]+dp[i-1])
    }
    // 得到 nums 的最大子数组
    res := math.MinInt32
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var maxSubArray = function(nums) {
    var n = nums.length;
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    var dp = new Array(n);
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (var i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    var res = Number.MIN_SAFE_INTEGER;
    for (var i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
};

🍭 代码可视化动画 🍭

以上解法时间复杂度是 O(N)，空间复杂度也是 O(N)，较暴力解法已经很优秀了，不过注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，那么我们可以施展前文动态规划的降维打击：空间压缩技巧讲的技巧进行进一步优化，将空间复杂度降低：

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;

    for (int i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的结果
        res = Math.max(res, dp_1);
    }
    
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;

    for (int i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的结果
        res = max(res, dp_1);
    }
    
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def maxSubArray(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0

    # 基础情况
    dp_0 = nums[0]
    dp_1 = 0
    res = dp_0

    for i in range(1, n):
        # dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = max(nums[i], nums[i] + dp_0)
        dp_0 = dp_1
        # 顺便计算最大的结果
        res = max(res, dp_1)

    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func maxSubArray(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    // base case
    dp_0 := nums[0]
    dp_1, res := 0, dp_0

    for i := 1; i < n; i++ {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = max(nums[i], nums[i]+dp_0)
        dp_0 = dp_1
        // 顺便计算最大的结果
        res = max(res, dp_1)
    }

    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 使用 var 声明一个函数 maxSubArray，参数为 nums 数组
var maxSubArray = function(nums) {
    var n = nums.length;
    if (n === 0) return 0;
    // 初始情况
    var dp_0 = nums[0];
    var dp_1 = 0, res = dp_0;

    for (var i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 同时计算最大值得结果
        res = Math.max(res, dp_1);
    }
    
    return res;
};

前缀和思路

在动态规划解法中，我们通过状态转移方程推导以 nums[i] 结尾的最大子数组和，其实用前文小而美的算法技巧：前缀和数组讲过的前缀和数组也可以达到相同的效果。

回顾一下，前缀和数组 preSum 就是 nums 元素的累加和，preSum[i+1] - preSum[j] 其实就是子数组 nums[j..i] 之和（根据 preSum 数组的实现，索引 0 是占位符，所以 i 有一位索引偏移）。

那么反过来想，以 nums[i] 为结尾的最大子数组之和是多少？其实就是 preSum[i+1] - min(preSum[0..i])。

所以，我们可以利用前缀和数组计算以每个元素结尾的子数组之和，进而得到和最大的子数组：

// 前缀和技巧解题
int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] preSum = new int[n + 1];
    preSum[0] = 0;
    // 构造 nums 的前缀和数组
    for (int i = 1; i <= n; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    
    int res = Integer.MIN_VALUE;
    int minVal = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        // 维护 minVal 是 preSum[0..i] 的最小值
        minVal = Math.min(minVal, preSum[i]);
        // 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
        res = Math.max(res, preSum[i + 1] - minVal);
    }
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 前缀和技巧解题
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> preSum(n + 1);
    preSum[0] = 0;
    // 构造 nums 的前缀和数组
    for (int i = 1; i <= n; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    
    int res = INT_MIN;
    int minVal = INT_MAX;
    for (int i = 0; i < n; i++) {
        // 维护 minVal 是 preSum[0..i] 的最小值
        minVal = min(minVal, preSum[i]);
        // 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
        res = max(res, preSum[i + 1] - minVal);
    }
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 前缀和技巧解题
def maxSubArray(nums: List[int]) -> int:
    n = len(nums)
    preSum = [0] * (n + 1)
    preSum[0] = 0
    # 构造 nums 的前缀和数组
    for i in range(1, n + 1):
        preSum[i] = preSum[i - 1] + nums[i - 1]

    res = float('-inf')
    minVal = float('inf')
    for i in range(n):
        # 维护 minVal 是 preSum[0..i] 的最小值
        minVal = min(minVal, preSum[i])
        # 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
        res = max(res, preSum[i + 1] - minVal)
    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 前缀和技巧解题
func maxSubArray(nums []int) int {
    n := len(nums)
    preSum := make([]int, n+1)
    preSum[0] = 0
    // 构造 nums 的前缀和数组
    for i := 1; i <= n; i++ {
        preSum[i] = preSum[i-1] + nums[i-1]
    }
    res := math.MinInt32
    minVal := math.MaxInt32
    for i := 0; i < n; i++ {
        // 维护 minVal 是 preSum[0..i] 的最小值
        minVal = min(minVal, preSum[i])
        // 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
        res = max(res, preSum[i+1]-minVal)
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var maxSubArray = function(nums) {
    var n = nums.length;
    var preSum = new Array(n + 1).fill(0);
    preSum[0] = 0;
    // 构造 nums 的前缀和数组
    for (var i = 1; i <= n; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    
    var res = Number.MIN_SAFE_INTEGER;
    var minVal = Number.MAX_SAFE_INTEGER;
    for (var i = 0; i < n; i++) {
        // 维护 minVal 是 preSum[0..i] 的最小值
        minVal = Math.min(minVal, preSum[i]);
        // 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
        res = Math.max(res, preSum[i + 1] - minVal);
    }
    return res;
};

至此，前缀和解法也完成了。

简单总结下动态规划解法吧，虽然说状态转移方程确实有点玄学，但大部分还是有些规律可循的，跑不出那几个套路。像子数组、子序列这类问题，你就可以尝试定义 dp[i] 是以 nums[i] 为结尾的最大子数组和/最长递增子序列，因为这样定义更容易将 dp[i+1] 和 dp[i] 建立起联系，利用数学归纳法写出状态转移方程。

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
256. Paint House🔒	256. 粉刷房子🔒
-	剑指 Offer 42. 连续子数组的最大和
-	剑指 Offer II 091. 粉刷房子

引用本文的文章

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释