DAY2

152. 乘积最大子数组
     给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

连续最大子数组和，子数组乘积，首先想到了动态规划的解法：
设一个数组dp,dp[i]为以第i个元素为结尾的最大乘积，状态转移方程则为dp[i]=max(dp[i]nums[i],nums[i]); 比较当前元素和前面最大乘积的积大小，找到以第i个元素为结尾的最大乘积。
但是由于存在负数，会使最大乘积变成最小，最小乘积变成最大，所以又维护了一个最小乘积数组，状态转移方程为dp_min=min(dp_min[i]nums[i],nums[i]);
当nums[i]为负数，则dp[i-1]变成dp_min[i-1].dp_min[i-1]变成dp[i-1]

class Solution {
public:
int maxProduct(vector<int>& nums) {
vector<int> dp; //动态规划
dp.resize(nums.size());
vector<int> dp_min(nums.size(),0);
int ma=nums[0];
//由于存在负数，需要维护最小值
int minmum=nums[0];
dp[0]=dp_min[0]=nums[0];
for(int i=1;i<nums.size();i++){
if(nums[i]<0){
int tem=dp[i-1];
dp[i-1]=dp_min[i-1];
dp_min[i-1]=tem;</int></int></int>

        }
        dp[i]=max(dp[i-1]*nums[i],nums[i]);
        dp_min[i]=min(dp_min[i-1]*nums[i],nums[i]);
        if(max(dp[i],dp_min[i])>ma) ma=max(dp[i],dp_min[i]);
    }
    return ma;
}

};