动态规划（最大乘积连续子串和最大和连续子串）

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存储局部最优值，即到i位置的最大和
max为全局最优值（不应从前缀和的角度考虑，应考虑正负）

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为局部最小值。由于乘积需要考虑正负的情况，即负负得正，因此需要记录局部最小值和局部最大值