Simple DP solution


  • 3
    M
    class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            vector<int> maxp;
            vector<int> minp;
            if(nums.size()==0) return 0;
            maxp.push_back(nums[0]);
            minp.push_back(nums[0]);
            for(int i = 1; i < nums.size(); i++)
            {
                maxp.push_back(max(max(nums[i],nums[i]*maxp[i-1]),nums[i]*minp[i-1]));
                minp.push_back(min(min(nums[i],nums[i]*maxp[i-1]),nums[i]*minp[i-1]));
            }
            return *max_element(maxp.begin(),maxp.end());
        }
        
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.