Notice
Recent Posts
Recent Comments
Link
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- ์ก๋ฆฌ๋จ
- ํ์ค์คํค
- ์กํ
- ์ ์ค์๋ด
- ์ ์ค
- ์ฝํ
- ์ ์ฅ
- javascript
- Sort
- ์๊ณ ๋ฆฌ์ฆ
- ์ฝ๋ฉํ ์คํธ
- ๋์ซ
- LeetCode
- ์ฐ์ฃผ
- ๊ฒ์
- ์ ํฌ๋ธ
- ๋ง์ง
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 152. Maximum Product Subarray ๋ณธ๋ฌธ
๋์ด๋ [ ๐ค ] 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 |
Comments