53. 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存儲(chǔ)局部最優(yōu)值，即到i位置的最大和
max為全局最優(yōu)值（不應(yīng)從前綴和的角度考慮，應(yīng)考慮正負(fù)）

152. 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為局部最小值。由于乘積需要考慮正負(fù)的情況，即負(fù)負(fù)得正，因此需要記錄局部最小值和局部最大值