53. 最大子数组和
3 min
题目
解法：动态规划
思路
核心思想是动态规划。定义dp[i]表示以第i个元素结尾的最大子数组和，通过状态转移方程dp[i]=max(nums[i], dp[i-1]+nums[i])递推求解。
正确性在于：以i结尾的最大子数组要么是当前元素本身，要么是当前元素加上以i-1结尾的最大子数组（若后者为正贡献）。遍历所有位置即覆盖全部连续子数组可能，确保不漏解。
- Step 1: 初始化dp[0]=nums[0]
- Step 2: 遍历i从1到n-1，计算dp[i]=max(nums[i], dp[i-1]+nums[i])
- Step 3: 遍历dp数组找出最大值返回
复杂度
- 时间复杂度: ，需遍历数组两次（计算dp和求最大值），线性时间瓶颈
- 空间复杂度: ，使用dp数组存储每个位置的最大子数组和
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int>dp(nums.size());
dp[0] = nums[0];
for(int i = 1 ;i < nums.size();i++){
dp[i] = max(dp[i-1]+nums[i],nums[i]);
}
int ans = dp[0];
for(int i = 0 ;i < nums.size();i++){
ans = max(ans,dp[i]);
}
return ans;
}
};