题目

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

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

解答

方法一:动态规划

问题分解

数组的子结构显然就是子数组。连续子数组类似滑动窗口,从前往后处理到某个元素时,要么并入前置子数组,要么自成一个子数组。

数组的所有连续子数组最大和,这个问题的最优子结构,可以定义为以某个元素结尾的连续子数组的最大和,这个子问题可以涵盖所有情况,并且可以推出问题的最优解。

最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。

状态定义

dp[i] 表示以 nums[i] 结尾的连续子数组最大和

状态转移

遍历到 nums[i]时,计算 dp[i]

  • nums[i] 并入以 nums[i-1]结尾的子数组:dp[i-1] + nums[i]
  • nums[i] 自成一个新的子数组:nums[i]

取二者最大值:dp[i] = max(dp[i-1]+nums[i], nums[i])

初始与返回

  • 初始化:dp[0] = nums[0],以nums[0] 结尾的连续子数组最大和即它本身。
  • 返回值:最终答案即为所有子问题的最优解,res=max(res,dp[i])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//动态规划
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=nums[0], n = nums.size();
vector<int> dp(n, 0); //dp[i]表示以nums[i]结尾的连续子数组最大和
dp[0] = nums[0];
for(int i=1;i<nums.size();++i){
dp[i] = max(dp[i-1]+nums[i], nums[i]); // 状态转移方程
res=max(res,dp[i]);
}
return res;
}
};

复杂度

  • 时间复杂度 O(n)
  • 空间复杂度 O(n) ,可以使用滚动变量代替dp数组,将空间复杂度降为 O(1)