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문제들을 풀고 있는데, 하면 할 수록 더 어려워진다.