动态规划巧解最大子数组和(Python，Java，C++)

题目LeetCode 53 最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

示例：

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

Python解法

动态规划

from typing import List class Solution: def maxSubArray(self, nums: List[int])->int: currentSum = nums[0] maxSum = nums[0] for i in range(1, len(nums)): currentSum = max(currentSum + nums[i], nums[i]) maxSum = max(maxSum, currentSum) return maxSum

1.定义值

cur = nums[0] # 当前子数组的最大和

max_sum = nums[0] # 全局最大和

2.循环核心

# 核心：要么重新开始，要么接着前面累加

cur = max(nums[i], cur + nums[i])

# 更新全局最大值

max_sum = max(max_sum, cur)

图形解释

Java解法

动态规划

道理同Python

class Solution{ public int maxSubArray(int[] nums){ int currentSum = nums[0]; int maxSum = nums[0]; for(int i = 1; i < nums.length; i++){ currentSum = Math.max(currentSum + nums[i], nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; } }

C++解法

动态规划

class Solution { public: int maxSubArray(vector<int>& nums) { int cur = nums[0]; int max_sum = nums[0]; for(int i = 1; i < nums.size(); i++){ cur = max(cur + nums[i], nums[i]); max_sum = max(max_sum, cur); } return max_sum; } };