Problem: 53. 最大子数组和
方法一:动态规划
思路
1.从传统暴力做法入手,枚举分析数学表达式
题目求所有任意连续子区间$[p,q]$和的最大值,即
$$max\left(\sum_{i=p}^{q} nums\left[i\right]\right),0\leq p\leq
q\leq n-1$$
显然可以使用$O(n^3)$的暴力算法求解(或者$O(n^2)$复杂度使用预处理前缀和+暴力)
2. 抽象出函数
考虑上面公式,它是一个关于数组长度$n$的函数:
$$
f(n-1)=max\left(\sum_{i=p}^{q} nums\left[i\right]\right),0\leq p\leq
q\leq n-1
$$
我们考虑下面一个问题:
(1).最终目标:
求任意$[0,n-1]$区间的最大连续和$f(n)$。
(2).分析转态之间关系:
对于某一前缀子区间$[0,q]$的最大连续和,即可以表示为$f(q)$。
但是由于函数相邻两项,$f[q-1]$与$f[q]$之间并不存在任何关系。具体来说,$f[q-1]$的最大连续区间和的区间终点,很有可能并不是以第$q-1$个元素作为结尾。
举个例子:
基于此,我们考虑以某一下标位置作为区间结尾的最大连续子区间和,并抽象出如下函数:
$$
F(q)=max\left(\sum_{i=p}^{q} nums\left[i\right]\right),0\leq p\leq
q
$$
请读者仔细比较$F(x)与f(x)$的区别,前者限制了区间终点的位置,后者没有限制。限制区间终点的位置是为了满足动态规划的“无后效性”,即当前状态的结果与后面的状态没有任何关系。 限制区间终点正是如此,每一个状态的结果必须是以当前下标为可能的区间终点。
3.列写状态转移方程
虽然$F$向后无关,但是$F$的值是向前相关的。对于每个$F(q)$,我们考虑$F(q-1)$,后者表达的是以$q-1$作为结尾的前缀区间($[0,q-1]$)中连续子区间的最大和。
由于后者的区间结尾是$q-1$,那么到第q个位置的时候,新的最大和应该考虑
(1) 把位置$q$合并到连续区间结尾
(2) 启程一段新的以$q$为首位置的连续区间
这两种操作之间,谁可以让$F(q-1)$获得更大的值。
即我们得到了状态转移方程:
$$
F(q)=max\bigg\{ F(q-1)+nums[q],\ \ nums[q]\bigg\}
$$
注意,我们要求解的实际上还是要求$f(n-1)$的值,比对他们实际意义,
$f(q-1)$表示某一前缀子区间$[0,q]$的最大连续和;
$F(q)$表示以q为区间结尾的前缀子区间的最大连续和。
可以发现:
$$
f(q)=max\bigg(F(i)\bigg),0\leq i \leq q
$$
题目中的目标结果$f(n-1)$就可以转化
$$
f(n-1)=max\bigg(F(i)\bigg),0\leq i \leq n-1
$$
以上我们完成了动态规划思想的所有步骤:状态函数、状态转移方程、最终结果与状态函数之间转移。
下面给出代码逻辑里的具体实现。
4.使用一维数组dp[]
存放$F(q)$的值
我们可以使用动态规划的思想,用某一个数组dp[]
记录。其中dp[i]
的值代表$F(q)$的值。
初始化时,dp[0]=nums[0]$
转态转移时,dp[i]=max(dp[i-1]+nums[i],nums[i]);
我们得到如下解题代码:
```C []
class Solution {
public:
int maxSubArray(vector[HTML_REMOVED]& nums) {
int n = nums.size();
//dp[0]即nums[0],这是因为题目要求至少有一个元素
vector[HTML_REMOVED] dp(n, 0); dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < n; i) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ans = max(dp[i], ans);
}
return ans;
}
};
# 复杂度
- 时间复杂度:
> 每个位置需要更新一次dp[i],$O(n)$
- 空间复杂度:
> 需要使用一维数组记录F[i]的值,$O(n)$
## 方法二:使用pre变量代替一维数组,优化空间复杂度
我们对于空间复杂度中使用了一个一维数组的方法并不满意。观察发现,每次`ans`的结果只和`dp[i]`相关,`dp[i]`只和`dp[i-1]`相关。
对这种状态转移只和前面前一个相邻量相关的情况,我们可以用某个变量,例如`int pre`来时刻存储`dp[i-1]`,然后更新`pre`的值,从而省去数组开销。
具体代码如下:
# Code
```C++ []
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int pre = nums[0]; //代替dp[]数组
int ans = nums[0];
for (int i = 1; i < nums.size();i++) {
pre = max(pre + nums[i], nums[i]);
ans = max(ans, pre);
}
return ans;
}
};
当然,我们也可以不去初始化ans,pre与nums的关联,合并到遍历能从0位置开始的情况。这样让代码看起来更简单,不过注意将ans初始化为一个比所有值都小的数。
C++
```C++ []
class Solution {
public:
int maxSubArray(vector[HTML_REMOVED]& nums) {
int pre = 0, ans = -10e6;
for (auto x : nums) {
pre = max(pre + x, x);
ans = max(ans, pre);
}
return ans;
}
};
## Python
```Python []
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre=0
ans=float("-inf")
for x in nums:
pre=max(pre+x,x)
ans=max(ans,pre)
return ans
复杂度
-
时间复杂度:
每个位置需要更新一次pre,$O(n)$
-
空间复杂度:
只需要一个常数空间。$O(1)$
方法三:贪心法
我们回顾上面方法中pre的含义:表示当前遍历到的位置为区间终点的前缀连续区间最大和。 意味着pre在更新时当前位置一定在区间中。
贪心法与方法二的本质区别在于,我们的pre更新的时候不考虑前一个相邻情况的pre,而是考虑需要更新pre的时候,拿到的pre是否为负数。
- 如果pre是负数,它对最终结果起到不利贡献,我们肯定不希望它合并到连续区间中。这种情况下,pre将更新为当前位置的值(不论当前位置是正还是负数)
- 反之,pre是非负数,则我们希望将当前位置并到前缀区间中。
总结成一句话:pre的更新丢弃负数,合并非负数。
代码如下:
C++
```C++ []
class Solution {
public:
int maxSubArray(vector[HTML_REMOVED]& nums) {
int pre = 0, ans = -10e6;
for (auto x : nums) {
//对于前端和为负数应该丢弃
pre = pre < 0 ? x : pre + x;
ans = max(pre, ans);
}
return ans;
}
};
## Python
```Python []
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre=0
ans=float("-inf")
for x in nums:
pre=x if pre<0 else pre+x
ans=max(ans,pre)
return ans