2015年10月15日星期四

Leetcode 152 Maximum Product Subarray

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.
Solution 1: Use DP and optimize the space to O(1), keep both max and min product, sometimes negtive number mult
 public class Solution {  
   public int maxProduct(int[] nums) {  
     int n=nums.length;  
     int max=0, min=0, res=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         max=nums[i];  
         min=nums[i];  
         res=nums[i];  
       }  
       else {  
         int maxNew=Math.max(nums[i],Math.max(nums[i]*max,nums[i]*min));  
         min=Math.min(nums[i],Math.min(nums[i]*max,nums[i]*min));  
         max=maxNew;  
         res=Math.max(res,max);  
       }  
     }  
     return res;  
   }  
 }  

没有评论:

发表评论