力扣链接：53. 最大子数组和，难度：中等。
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2:
输入: nums = [1]
输出: 1
解释: The subarray [1] has the largest sum 1.
示例 3:
输入: nums = [5,4,-1,7,8]
输出: 23
解释:
The subarray [5,4,-1,7,8] has the largest sum 23.
约束:
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
思路
- 本题可以用贪心算法解决（请看
方案2），不过这里我们使用另一种方法。 - 假设
nums的大小为i，我们考虑将同样的问题应用到nums的子数组中，从索引0到i - 1。 - 答案是肯定的。那么我们再想想
i - 1的答案是否会影响i的答案。 - 答案仍然是肯定的。那会有什么影响呢？对于nums[i]，
- 如果
上一次的和为负数，我们可以丢弃上一次的和； - 如果
上一次的和为正数，我们可以将上一次的和加到当前和中。
- 如果
- 所以我们可以使用
动态规划来解决这个问题。 “动态规划”算法的特点是，dp[i]的值由dp[i - 1]转化而来。
“动态规划”的模式
“动态规划”分为五步
- 确定数组
dp的每个值代表的含义。 - 初始化数组
dp的值。 - 根据一个示例，“按顺序”填入
dp网格数据。 - 根据
dp网格数据，推导出“递推公式”。 - 写出程序，并打印
dp数组，不合预期就调整。
细说这五步
- 确定数组
dp的每个值代表的含义。- 先确定
dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个对等数组”，为了理解方便，还是使用“二维数组”。 - 尝试使用问题所求的
返回值的含义作为dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。 - 设计上尽量考虑保存更丰富的信息，重复信息只在某个
dp[i]中保存一次就够了。 - 使用简化的含义。如果用
布尔值可以解决问题，就不要用数值。
- 先确定
- 初始化数组
dp的值。dp的值涉及两个层面：dp的长度。通常是：条件数组长度加1或条件数组长度。dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
- 根据一个示例，“按顺序”填入
dp网格数据。- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入
dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。 - 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写
dp网格数据，这也是在模拟程序处理的过程。 - 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
- 根据
dp网格数据，推导出“递推公式”。- 有三个特别的位置需要注意：
dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的dp[i][j]往往取决于它们。 - 操作“两个对等数组”时，因为对称性，我们可能需要同时使用
dp[i - 1][j]和dp[i][j - 1]。
- 有三个特别的位置需要注意：
- 写出程序，并打印
dp数组，不合预期就调整。- 重点分析那些不合预期的数值。
读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗
步骤
动态规划的常用步骤
这五个步骤是解决动态规划问题的模式。
- 确定
dp[i]的含义- 首先，尝试使用问题的
return值作为dp[i]的值来确定dp[i]的含义。如果不行，请尝试另一种方法。 - 假设
dp[i]表示索引i处的最大和。这样做行吗？点击查看答案
dp[i + 1]无法通过dp[i]计算。所以我们必须改变这个含义。 - 该如何设计呢？
点击查看答案
如果
dp[i]表示索引i处的当前和，dp[i + 1]就可以通过dp[i]计算。最后，我们就可以看到最大和记录在当前和数组中。
- 首先，尝试使用问题的
确定
dp数组的初值使用示例：
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] dp = [-2, 1, -3, 4, -1, 2, 1, -5, 4]dp[i] = nums[i]就好。
确定
dp数组的递归公式尝试完成
dp数组。在此过程中，您将获得推导公式的灵感。nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] dp = [-2, 1, N, N, N, N, N, N, N] # N 表示现在不关注 dp = [-2, 1, -2, N, N, N, N, N, N] dp = [-2, 1, -2, 4, N, N, N, N, N] dp = [-2, 1, -2, 4, 3, N, N, N, N] dp = [-2, 1, -2, 4, 3, 5, N, N, N] dp = [-2, 1, -2, 4, 3, 5, 6, N, N] dp = [-2, 1, -2, 4, 3, 5, 6, 1, N] dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]分析完示例
dp数组，我们可以得出递归公式:dp[i] = max(nums[i], dp[i - 1] + nums[i])
确定
dp数组的遍历顺序dp[i]依赖于dp[i - 1]，所以我们应该从左到右遍历dp数组。
检查
dp数组的值- 打印
dp看看是否符合预期。
- 打印
复杂度
时间复杂度
O(n)
空间复杂度
O(n)
Python #
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = nums.copy()
for i in range(1, len(dp)):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp)
Java #
class Solution {
public int maxSubArray(int[] nums) {
var dp = nums.clone();
for (var i = 1; i < dp.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
}
return IntStream.of(dp).max().getAsInt(); // if you want to beat 99%, refer to C# soluiton's comment
}
}
JavaScript #
var maxSubArray = function (nums) {
const dp = [...nums]
for (let i = 1; i < dp.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
}
return Math.max(...dp)
};
Go #
func maxSubArray(nums []int) int {
dp := slices.Clone(nums)
for i := 1; i < len(nums); i++ {
dp[i] = max(nums[i], dp[i - 1] + nums[i])
}
return slices.Max(dp)
}
Ruby #
def max_sub_array(nums)
dp = nums.clone
(1...dp.size).each do |i|
dp[i] = [ nums[i], dp[i - 1] + nums[i] ].max
end
dp.max
end
C# #
public class Solution
{
public int MaxSubArray(int[] nums)
{
var dp = (int[])nums.Clone();
for (var i = 1; i < dp.Length; i++)
{
dp[i] = Math.Max(nums[i], dp[i - 1] + nums[i]);
}
return dp.Max(); // if you want to beat 99%, you can use a variable to collect the maximum value: `if (dp[i] > result) result = dp[i];`
}
}
C++ #
class Solution {
public:
int maxSubArray(vector<int>& nums) {
auto dp = nums;
for (auto i = 1; i < dp.size(); i++) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
}
return *max_element(dp.begin(), dp.end());
}
};
其它语言
欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 53. 最大子数组和。题解2的思路：贪心算法（滚动变量）
- 本题的“贪心”算法解法和“动态规划”算法解法在本质上是一样的，都是“动态规划”，只不过此处的“贪心”算法把从使用
dp一维数组，再降一个维度，变成了只使用两个变量。 - 此处的“贪心”算法可以被称为“滚动变量”。就像“滚动数组（一维）”对应的是二维数组一样，一滚动就能降一个维度。
复杂度
时间复杂度
O(N)
空间复杂度
O(1)
Python #
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
result = -float('inf')
pre_sum = 0
for num in nums:
pre_sum = max(pre_sum + num, num)
result = max(result, pre_sum)
return result
C++ #
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT_MIN;
int pre_sum = 0;
for (int num : nums) {
pre_sum = max(pre_sum + num, num);
result = max(result, pre_sum);
}
return result;
}
};
Ruby #
# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
result = -Float::INFINITY
pre_sum = 0
nums.each do |num|
pre_sum = [pre_sum + num, num].max
result = [result, pre_sum].max
end
result
end
Go #
func maxSubArray(nums []int) int {
result := math.MinInt
preSum := 0
for _, num := range nums {
preSum = max(preSum + num, num)
if preSum > result {
result = preSum
}
}
return result
}
JavaScript #
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let result = -Infinity;
let preSum = 0;
for (const num of nums) {
preSum = Math.max(preSum + num, num);
result = Math.max(result, preSum);
}
return result;
};
C# #
public class Solution
{
public int MaxSubArray(int[] nums)
{
int result = int.MinValue;
int preSum = 0;
foreach (int num in nums)
{
preSum = Math.Max(preSum + num, num);
result = Math.Max(result, preSum);
}
return result;
}
}
Java #
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int preSum = 0;
for (int num : nums) {
preSum = Math.max(preSum + num, num);
result = Math.max(result, preSum);
}
return result;
}
}