2014年10月1日 星期三

[LeetCode] Maximum Product Subarray

Problem:
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:O(n)
public class Solution {
    public int maxProduct(int[] A) {
        if(A.length == 1)
            return A[0];
            
        int max = A[0];
        int premax = Math.max(A[0],0);
        int premin = Math.min(A[0],0);
        for(int i=1; i=0){
              premax = (premax ==0?A[i]: A[i]*premax);
              premin = (premin ==0?0: A[i]*premin);
            }
            else{
              int tmp = (premin ==0? 0 : A[i]*premin);
              premin = (premax > 0? A[i]*premax: A[i]);
              premax = tmp;
            }
            max = Math.max(max,premax);
        }
        return max;
    }
}

沒有留言:

張貼留言