152. Maximum Product Subarray

💡 풀이

var maxProduct = function (nums) {
  if (nums.length === 1) return nums[0];

  let minDp = new Array(nums.length).fill(1);
  let maxDp = new Array(nums.length).fill(1);

  minDp[0] = nums[0];
  maxDp[0] = nums[0];

  for (let i = 1; i < nums.length; i++) {
    let cur = nums[i];

    minDp[i] = Math.min(minDp[i - 1] * cur, maxDp[i - 1] * cur, cur);
    maxDp[i] = Math.max(minDp[i - 1] * cur, maxDp[i - 1] * cur, cur);
  }

  // console.log('minDp: ', minDp);
  // console.log('maxDp: ', maxDp);

  // console.log(Math.max(...minDp, ...maxDp));

  return Math.max(...maxDp);
};

📝 정리

이전에 풀었던 카데인 알고리즘을 이용해 풀었다. 이전 문제와 가장 두드러지는 차이점은 두 개의 dp 배열을 만들었다는 점이다.

이 문제를 풀기 위해 최소값을 저장한 minDp 배열과 최댓값을 저장한 maxDp 배열을 두개 만들었다. 이후 점화식 minDp에 관련된 Math.min(minDp[i - 1] * cur, maxDp[i - 1] * cur, cur), maxDp에 관련된 Math.min(minDp[i - 1] * cur, maxDp[i - 1] * cur, cur)를 생성하였다.

만약 한 개의 점화식으로 풀었을 경우, nums 배열이[-2, -3, 4] 이와 같이 주어질 경우, 최댓값을 3으로 도출한다. 실제 도출해야 될 최댓값은 -2 * -3 * 4인 24이다. (내가 처음 풀었을 때 틀렸던 이유)

수정, 지적을 환영합니다!

위 문제에 대한 설명은 '코드없는 프로그래밍 - Youtube' 를 참조하였습니다.

문제 링크

https://leetcode.com/problems/maximum-product-subarray/

LeetCode GitHub

https://github.com/tTab1204/LeetCode