Leetcode53. 最大子数组和(HOT100)
链接
我的解法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int res = INT_MIN;
vector<int> f(n+1,0);
for(int i = 1;i<=n;i++){
f[i] = max(f[i-1]+nums[i-1],nums[i-1]);
res = max(res,f[i]);
}
return res;
}
};
f[i]表示以nums[i]结尾的子数组的和的最大值。
对于前i个数，要求最大和，要么就是前i-1个数求出来的最大和，要么是第i个数本身就是这i个数中的最大和。
更好的解法：
// class Solution {
// public:
// int maxSubArray(vector<int>& nums) {
// int res = INT_MIN;
// for(int i = 0,last = 0;i<nums.size();i++){
// last = max(nums[i],nums[i]+last);
// res = max(res,last);
// }
// return res;
// }
// };空间复杂度是O(1)的，使用last来存储f[i-1],每次更新last。