leetcode 152. Maximum Product Subarray (最大连续子序列乘积,dp)

Posted by 111qqz on Friday, April 14, 2017

TOC

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

思路:由于有正,有负,还有0.。。所以比最大子串之和要复杂一些。。。

dp[i].max表示到当前位置的最大乘积。

dp[i].min表示到当前位置的最小乘积。

dp[i].max = max{dp[i-1].maxa[i],dp[i-1].mina[i],a[i]};

dp[i].min同理

边界dp[i].max = dp[i].min = a[0]

/* ***********************************************
Author :111qqz
Created Time :2017年04月14日 星期五 18时57分13秒
File Name :152.cpp
************************************************ */
class Solution {

public:

    //dp
    //dp[i]表示当前的最大乘积。
    //用了滚动数组优化空间/
    int maxProduct(vector<int>& nums) {
    int siz = nums.size();
    int mnpre,mncur,mxpre,mxcur;
    int ret;
    ret = mnpre = mncur = mxpre = mxcur = nums[0];
    for ( int i = 1 ; i < siz ; i++ )
    {
        mncur = min(nums[i],min(nums[i]*mnpre,nums[i]*mxpre));
        mxcur = max(nums[i],max(nums[i]*mnpre,nums[i]*mxpre));
        ret = max(ret,mxcur);
        mnpre = mncur;
        mxpre = mxcur;
    }
    return ret;
	
    }

};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付