[动态规划简单题] LeetCode 53. 最大子数组和

LeetCode 53. 最大子数组和

我不自闭！加油加油！
https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

参照该 up 的解法
https://www.bilibili.com/video/BV1XR4y1j7Lo/
题目分析五步走

1. 设计状态

dp[i] 表示以第 i 个整数结尾的子数组中的最大子数组和。

以第 i 个整数结尾的子数组分为两种情况：

• 和第 i-1 个整数结尾的子数组相连
• 单独以第 i 个整数作为子数组

举例：[1, -3, 2]

• 以 -3 为结尾的子数组最大子数组和为 max(1+(-3), -3) = -2
• 以 2 为结尾的子数组最大子数组和为 max((1+(-3)+2), 2) = 2

2. 写出状态转移方程

dp[i] = max(dp[i-1]+nums[i], nums[i])

3. 设定初始状态

dp[0] = nums[0]

4. 执行状态转移

5. 返回最终的解

Solution

// 取最大值
int max(int a, int b) {
    
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    
    int dp[100001];
    // 初始状态
    dp[0] = nums[0];
    int maxValue = nums[0];
    for(int i = 1; i < numsSize; ++i) {
    
	    // 执行状态转移
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        maxValue = max(dp[i], maxValue);
    }
    // 返回最终解
    return maxValue;
}

Solution(Python)

使用 Python 实现轮换法更简洁

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        pre, max_value = 0, nums[0]
        for value in nums:
            pre = max(pre + value, value)
            max_value = max(max_value, pre)
        return max_value