[leetcode]53. Maximum Subarray

문제

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

제한사항

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

풀이

1차풀이

function solution(nums) {
   let max = Number.MIN_SAFE_INTEGER;
   let maxArray = [];
   for (let i = 0; i < nums.length; i++) {
     for (let j = i + 1; j < nums.length + 1; j++) {
       const array = nums.slice(i, j);
       const num = array.reduce((acc, cur) => acc + cur, 0);

       max = max < num ? num : max;
     }
   }
   return max;
 }

문제점

for문을 두번 돌렸기에 마지막 제한사항이었던 O(n)을 위배해 제한사항에 걸리게 된다.

2차풀이

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

  for (let i = 1; i < n; i++) {
    if (dp[i - 1] < 0) {
      dp[i] = nums[i];
    } else {
      dp[i] = dp[i - 1] + nums[i];
    }
  }
  
  return Math.max(...dp);
}

for문을 1번이용하여 풀기 위해서는 이전 값들을 저장하고, 비교하여 문제를 풀어야한다는 생각이 들어 dp를 활용하게 되었다. 전의 값을 dp Array에 저장하고, 전 값이 양수면 계속 합해나가고, 음수가 되면 더하지 않는다.

느낀점

Easy 문제를 풀었음에도 풀구하고 효율성, O(n)관련 제한사항이 걸려있어서 당황스러웠고, 생각을 많이 하게 되었다. dp, 혹은 조금 더 효율적으로 풀수 있는 방법에 대해선 거의 생각해보지 않았는데, 앞으로 문제를 플이할 때, 풀이하고 나서 효율적인 방법을 고민해 보아야 겠다.