C++ simple DP O(N) RT, O(1) Space


  • 0
    G
    class Solution {
    public:
        int maxProduct(vector<int>& nums) 
        {
            int Pos = 0;
            int Neg = 0;
            int Max = INT_MIN;
            
            if(nums.size() == 1)
            {
                return (nums[0]);
            }
            
            for(int i = 0; i < nums.size(); ++i)
            {
                if(nums[i] > 0)
                {
                    Pos = max(nums[i],Pos*nums[i]);
                    Neg = nums[i]*Neg;
                    
                    Max = max(Max,Pos);
                    
                }
                else if(nums[i] < 0)
                {
                    int Prev = Pos;
                    Pos = Neg*nums[i];
                    Neg = min(Prev*nums[i],nums[i]);
                    Max = max(Max, Pos);
                }
                else
                {
                    Pos = 0;
                    Neg = 0;
                }
            }
            
            return (Max);
        }
    };

Log in to reply
 

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