- Maximum Subarray：https://leetcode.com/problems/maximum-subarray/description/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n);
dp[0]=nums[0];
int max=nums[0];
for(int i=1;i<n;i++){
dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
max=max>dp[i]?max:dp[i];
}
return max;
}
};
dp存储局部最优值，即到i位置的最大和
max为全局最优值（不应从前缀和的角度考虑，应考虑正负）
- Maximum Product Subarray: https://leetcode.com/problems/maximum-product-subarray/description/
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n=nums.size();
vector<int>first(n);
vector<int>last(n);
first[0]=nums[0];
last[0]=nums[0];
for(int i=1;i<n;i++){
first[i]=max(max(nums[i],nums[i]*first[i-1]),nums[i]*last[i-1]);
last[i]=min(min(nums[i],nums[i]*first[i-1]),nums[i]*last[i-1]);
}
int m=nums[0];
for(int i=0;i<n;i++){
m=max(m,first[i]);
}
return m;
}
};
first为局部最大值，last为局部最小值。由于乘积需要考虑正负的情况，即负负得正，因此需要记录局部最小值和局部最大值
