Voyz's Studio.

LeetCode算法笔记--乘积最大子数组

字数统计: 239阅读时长: 1 min
2021/01/22 Share

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.

方法一:动态规划

2mww7-1b4ro.gif

1
2
3
4
5
6
7
1.令imax为当前最大值,则当前最大值为 imax = max(imax * nums[i], nums[i])

2.由于存在负数,那么会导致最大的变最小的,最小的变最大的。因此还需要维护当前最小值imin,imin = min(imin * nums[i], nums[i])

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
/**
* @param {number[]} nums
* @return {number}
*/
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;
};
CATALOG
  1. 1. LeetCode算法笔记-Day63
    1. 1.1. 152. Maximum Product Subarray
    2. 1.2. 方法一:动态规划
      1. 1.2.1. Answer: