LeetCode算法笔记-Day63
152. Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
1
2
3
4
5
6
7
8
9
10
| Example:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
|
方法一：动态规划
1
2
3
4
5
6
7
| 1.令imax为当前最大值，则当前最大值为 imax = max(imax * nums, nums)
2.由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums, nums)
3.当负数出现时则imax与imin进行交换再进行下一步计算
时间复杂度：O(n)
|
Answer：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
var maxProduct = function(nums) {
let res = -1*Infinity,
curr_max = 1,
curr_min = 1;
for(let i=0;i<nums.length;i++){
if(nums[i]<0){
[curr_max,curr_min] = [curr_min,curr_max];
}
curr_max = Math.max(curr_max * nums[i],nums[i]);
curr_min = Math.min(curr_min * nums[i],nums[i]);
res = Math.max(res,curr_max);
}
return res;
};
|
