[ LeetCode_152 ] Maximum Product SubArray ( by using JavaScript )

Problem

Solve

 

1) DP

 

이전에 풀었던 덧셈 문제처럼, 각 자리에서 얻을 수 있는 최선의 결과만을 구하려고 하니 < 음수 * 음수 > 의 문제를 해결해주지 못해서 결과가 올바르게 나오지 않았다 :) 

 

function solution(nums) {
  
  let answer = 0;
  let dp = Array(nums.length).fill(0);
  dp[0] = nums[0];

  for (let i = 1; i < nums.length; i++) {
    let prevDp = dp[i - 1] * nums[i];
    let prevNums = nums[i - 1] * nums[i];
    dp[i] = Math.max(nums[i], prevDp, prevNums);
  }
  
  answer = Math.max(...dp);
  return answer;

}

 

2) isOdd 

 

이전의 문제를 해결 하려고 도전하다보니, 찾아낸 방법은 음수가 짝수 일 때는 음수 값을 곱하고, 만약 홀수라면 곱하지 않고 그 자리의 값을 채용하는 방법을 선택했다. 

 

하지만, 그러다보니 음수만 나왔을 때 이를 제대로 처리 하지 못하는 문제가 발생하였다.

 

function solution(nums) {

  let isOdd = false;
  let result = 0;
  let oddCount = nums.filter((num) => num < 0);

  if (oddCount % 2 === 0) {
    isOdd = true;
  }

  for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] < 0 || nums[i] < 0) {
      if (isOdd) {
        nums[i] = nums[i - 1] * nums[i];
      }
    } else {
      if (nums[i - 1] !== 0) {
        nums[i] = nums[i - 1] * nums[i];
      }
    }
  }
  console.log(nums);
  result = Math.max(...nums);
  return result;
    
};

 

3) Min, Max

 

작은 값과 큰 값을 나누어 변수를 선언한 후, 음수를 하면 두 값을 교환하는 방법으로 문제를 해결하였다.

실제로 내가 푼 것은 아니고 풀이를 참조하여 풀었는데 이 문제는 꼭 다시 풀어야겠다는 생각을 하였다 :(

 

function solution(nums) {

  let maxSoFar = nums[0];
  let minSoFar = nums[0];
  let res = nums[0];

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

    if (nums[i] < 0) {
      let tmp = maxSoFar;
      maxSoFar = minSoFar;
      minSoFar = tmp;
    }

    maxSoFar = Math.max(maxSoFar, nums[i]);
    minSoFar = Math.min(minSoFar, nums[i]);
    res = Math.max(res, maxSoFar);
  }
  return res;

}