.Zzumbong

[leetCode/JS] 152. Maximum Product Subarray ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 152. Maximum Product Subarray

์ญ˜๋ด‰ 2022. 12. 14. 10:53

๋‚œ์ด๋„ [ ๐Ÿค” ] Medium

 

๋ฌธ์ œ ์„ค๋ช… 

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

 

์—ฐ์†๋œ element ์ค‘ ๊ณฑํ–ˆ์„ ๋•Œ, ๊ฐ€์žฅํฐ ์ˆ˜๋ฅผ return ํ•œ๋‹ค.

 

 

 

์ž…์ถœ๋ ฅ ์˜ˆ

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

 

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

 

Constraints

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

 

 


 

๋‚ด ์†”๋ฃจ์…˜

  • array์—์„œ ๋ญ”๊ฐ€ ํ•ฉ์ณค์„ ๋•Œ, ๊ฐ€์žฅ ํฐ ์ˆ˜, ๊ฐ€์žฅ ์ž‘์€ ์ˆ˜ ๋ฅผ ๊ตฌํ•ด๋ผ ์ด๋Ÿฐ๊ฑด ๋Œ€๋ถ€๋ถ„ DP๋กœ ํ‘ผ๋‹ค.
  • ์ฒ˜์Œ์—” ๊ฐ€์žฅ ํฐ ์ˆ˜ ์ฐพ๊ธฐ ๋ผ๊ณ  ์ƒ๊ฐํ•ด์„œ nums[i-1] * nums[i] ์™€ nums[i]์™€ max ์ค‘ ํฐ ์ˆ˜๋ฅผ max์— ๋„ฃ์—ˆ๋‹ค.
var maxProduct = function(nums) {
  let max = nums[0];
  for(let i = 1; i < nums.length; i++) {
    max = Math.max(max, nums[i], nums[i-1] * nums[i]);
  }
  return max;
};
  • ๊ณ ๋ คํ•˜์ง€ ๋ชปํ•œ ์ƒํ™ฉ์ด [-2, 3, -4] ์ฒ˜๋Ÿผ ์Œ์ˆ˜๋ผ๋ฆฌ ๊ณฑํ–ˆ ์„๋•Œ, ๊ฐ€์žฅ ํฐ ์ˆ˜๊ฐ€ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์ด๋‹ค
var maxProduct = function(nums) {
  let max = nums[0];
  let prevMin = nums[0];
  let prevMax = nums[0];
  for(let i = 1; i < nums.length; i++) {
    const curMin = prevMin * nums[i];
    const curMax = prevMax * nums[i];
    prevMax = Math.max(nums[i], curMin, curMax);
    prevMin = Math.min(nums[i], curMin, curMax);
    max = Math.max(max, prevMax);
  }
  return max;
};
  • ์™„์„ฑ๋ณธ.

 

 

 

๊ฐ์ƒํ‰

  • ๋Œ€๋ถ€๋ถ„์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์˜ ๊ฐœ๋…๋“ค์€ ์ฐธ ์‰ฌ์šด๋ฐ..
  • ์ฝ”๋“œ๋กœ ๋ณด๋ฉด ๊ฐœ๊ฐ™์ด ์–ด๋ ต๋‹ค.
  • DP๊ฐ€ ์–ด๋ ค์›Œ์„œ DP๋ฌธ์ œ๋“ค์„ ํ’€๊ณ  ์žˆ๋Š”๋ฐ, ํ•˜๋ฉด ํ•  ์ˆ˜๋ก ๋” ์–ด๋ ค์›Œ์ง„๋‹ค.

 

'coding test > leetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[leetCode/JS] 232. Implement Queue using Stacks  (0) 2022.12.16
[leetCode/JS] 1143. Longest Common Subsequence  (0) 2022.12.15
[leetCode/JS] 198. House Robber  (0) 2022.12.14
[leetCode/JS] 931. Minimum Falling Path Sum  (0) 2022.12.13
[leetCode/JS] 70. Climbing Stairs  (0) 2022.12.12
0 Comments
๋Œ“๊ธ€์“ฐ๊ธฐ ํผ