leetcode 152 maximun 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.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class  {
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,保存当前存到的最大值和最小值,每次更新最大值。