LeetCode 53 最大子数组和 - 动态规划解法
https://leetcode.cn/problems/maximum-subarray/description/
思路
暴力穷举
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=INT_MIN;
for(int index =0;index<nums.size();index++){
for(int len = 0;len+index<nums.size();len++){
int sum = 0;
for(int j = index;j<=index+len;j++){
sum+=nums[j];
}
res = max(sum,res);
}
}
return res;
}
};
动规
第一次做这题时，动规思路并不清晰。复盘后可以这样理解：
这题的答案不是 dp 数组最后一个位置的值，而是从所有状态中按规则（这里取最大值）选出来。因此，dp 数组（或递归函数）的语义本质是“状态分类”，关键是怎么分。
这里的分类方式是：以 index 开头的子数组最大和。不同 index 之间存在递推关系，所以可以使用递归/动态规划。
穷举所有情况->分类->加上最优性质->各个类别之间产生关系。
递归
class Solution {
public:
int res = INT_MIN;
int get_max(vector<int> nums,int index){
if(index==nums.size()) return 0;
int tmp = get_max(nums,index+1);
if(tmp<0){
res = max(res,nums[index]);
return nums[index];
}else{
res = max(res,nums[index]+tmp);
return nums[index]+tmp;
}
}
int maxSubArray(vector<int>& nums) {
get_max(nums,0);
return res;
}
};
动规
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_value = INT_MIN;
vector<int> re_value = vector<int>(nums.size()+1,INT_MIN);
re_value[nums.size()] = 0;
for(int i = nums.size()-1;i>=0;i--){
re_value[i+1]>0?re_value[i] = nums[i]+re_value[i+1]:re_value[i] = nums[i];
max_value = max(max_value,re_value[i]);
}
return max_value;
}
};
发现for循环内 只依赖 i+1 ，因此可以只维护一个变量：last。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_value = INT_MIN;
int last =0;
for(int i = nums.size()-1;i>=0;i--){
last>0?last = nums[i]+last:last = nums[i];
max_value = max(max_value,last);
}
return max_value;
}
};