[LeetCode_53] Maximum SubArray ( by using JavaScript)

Problem

 

연속된 배열에서 얻을 수 있는 최대 값을 얻어내라.

 

접근법

 

1-1) O(n^2)

 

이 단계는 구현도 하지 않았는데, 그 이유는 무조건 시간 초과가 뜰 것이기 때문이다.

그리고, 이번 코딩테스트를 준비하며 동기 형에게 얻은 꿀팁은 어떻게하면 O(n) 으로 문제를 풀 수 있을까? 고민을 하라는 것이였는데 이에 따라 첫번째 단계는 손을 대지 않았다.

 

1-2) DP [ O(n) ] 

 

이 문제를 쉽게 생각하면 배열 전체를 바라보는 것이 아니라, 각 배열의 자리에서 얻을 수 있는 최선의 값을 얻는 것이 좋다고 생각을 하였다.

 

그렇다면 어떤 접근법이 좋은걸까? 고민을 해보게 되었는데, 자리 별로 최선의 값을 저장하고 이를 이용하는 방법 "DP"가 떠올랐다.

 

점화식을 고민 해보다가, 직접 DP를 해보면서 접근을 한 결과를 얻을 수 있었는데 내가 세운 점화식은 다음과 같다.

 

[1] i 

 

[2] dp(i-1) + i 

 

[3] nums(i-1)  + i

 

중 최대 값을 뽑아내면 됬고 88ms 라는 결과 값을 얻을 수 있었다.

function solution() {
  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;
}

let nums = [-2, -1];
console.log(solution());

 

1-3 ) More JavaScirptive 

 

dp로 문제를 풀고 나니, 더 자바스크립트스럽게 풀 수는 없을까? 라는 생각을 가지고 방법을 찾다가  Kadane’s Algorithm 를 알게 되었다.

 

위의 알고리즘은 부분 집합 중 최대 값을 쉽게 구해내는 알고리즘 인데, 이 알고리즘을 쉽게 말해보자면 "이전 값이 양수 일때만 더하는 알고리즘" 이라 할 수 있습니다.

 

아래의 배열을 예시로 solution 배열의 값을 출력하면 [-2, 1, -2, 4, 3, 5, 6,  1, 5 ] 과 같이 나오는데

DP와 비슷한 방법이지만 "이전 값이 양수일때만 더한다" 라는 방법을 통해 더욱 자바스크립트스럽게 해결 할 수 있는 방법을 찾을 수 있게 되었습니다. 

function solution() {
  nums.forEach((value, index) => {
    if (nums[index - 1] > 0) {
      nums[index] = value + nums[index - 1];
    }
  });

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

let nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(solution());