leetcode 152 Maximun Product Subarray
z
 2018-03-07 23:38:54  

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int max = nums[0];
        int min = nums[0];
        int ans = max;
        for(int i=1; i<n; i++){
            int t = max;
            max = Math.max(Math.max(max*nums[i], min*nums[i]), nums[i]);
            min = Math.min(Math.min(t*nums[i], min*nums[i]), nums[i]);
            ans = Math.max(max, ans);
        }
        return ans;
        
    }
}
  • 遍历一遍数组，设定一个max和min，保存当前存到的最大值和最小值，每次更新最大值。