Java dynamic programming solution [Accepted]


  • 0
    P

    class Solution {
    public int maxProduct(int[] nums) {
    int n = nums.length;

        int[] optmax = new int[n];
        
        int[] optmin = new int[n];
        
        optmax[0] = nums[0];
        optmin[0] = nums[0];
            
        
        
        for(int i = 1; i < n; i++)
        {
            optmin[i] = Math.min(optmin[i-1]*nums[i], Math.min(nums[i], optmax[i-1]*nums[i]));
            optmax[i] = Math.max(optmax[i-1]*nums[i], Math.max(nums[i], optmin[i-1]*nums[i]));
            
        }
        
        int max = optmax[0];
        
        for (int i = 1; i < n; i++)
            max = Math.max(max,optmax[i]);
        return max;
    }
    

    }


Log in to reply
 

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