53 最大子数组和
前缀和
看到连续子数组的和会想到使用前缀和
但是不同的地方在于,我们需要保证连续子数组的和最大,也就是说假设区间[j,i]的和最大,sum[i] - sum[j - 1]最大
当我们遍历到i时,sum[i]可以i通过sum[i] = sum[i - 1] + num[i]获得,因此我们可以将其看作是定值
那么想要和最大,就需要sum[j - 1]最小,方法也很简单,只需要遍历的时候维护一个最小值前缀和preMin即可
值得注意的是,计算顺序不能乱,必须是:
- 计算前缀和pre
- 计算连续子数组和ans
- 更新最小前缀和
如果Step2 和 Step3顺序交换,那么会出现sum[i] - sum[j]的情况,对应的区间是空的,而本题要求子数组至少含有一个元素
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0;
// preMin初始化需要为0
// 保证第一个元素的ans为pre
int preMin = 0;
// ans可能为负数,因此需要定义为最小值
int ans = INT_MIN;
for(int num : nums){
// 更新前缀和
pre += num;
ans = max(ans, pre - preMin);
preMin = min(preMin, pre);
}
return ans;
}
};
- 时间复杂度:O(n),其中 n 为 nums 的长度。
- 空间复杂度:O(1)。仅用到若干额外变量
动态规划
思路也很简单:
- 因为连续子数组的和是否取当前元素,取决于本元素前的元素的连续子数组的和,这符合动态规划
dp[i]表示nums[i]结尾的子数组的和的最大值- 递推公式
dp[i] = max(dp[i - 1], 0) + nums[i]- 如果前一个元素为负数,那么加上这个元素之后,连续子数组的和只会更小
- 只有前一个元素为非负数,加上这个元素之后,连续子数组的和才会更大
- 初始化:
dp[0]表示nums[0]结尾的子数组的和的最大值,也就是nums[0] - 遍历顺序:从左到右