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