Maximum Subarray

53. Maximum Subarray

subarray란 전체 배열안에 연속된 부분 배열을 의미한다. 즉, 전체 배열에서 부분 배열의 가장 큰 합을 구하는 문제이다.

배열에 음수가 없다면, 최대 부분 배열의 합은 전체 배열의 합이다. 배열에 양수가 없다면, 가장 큰 음수 하나이며 조건에 따라 빈 배열이 될 수 있다.

문제

모든 부분 배열의 합을 비교하는 완전 탐색(Brute force)로 문제를 풀었는데, DP(Kadane 알고리즘)로 푼 해설을 보고 알아보았다.

테스트 케이스

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Brute-force 접근

완전 탐색으로 모든 subarray의 합 중 가장 큰 값을 출력할 수 있다. i와 j는 모든 부분 배열을 탐색하고 k는 부분 배열의 합을 구한다. 시간 복잡도는 O(n^3)이 될 것이다.

var maxSubArray = function(nums) {
  if (nums=== null || nums.length === 0) return 0

  let maxSum = nums[0]

  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let currSum = 0;
      for (let k = i; k <= j; k++) {
        currSum += nums[k];
      }
      maxSum = Math.max(maxSum, currSum)
    }
  }
  return maxSum
}

maxSubArray([-2,1,-3,4,-1,2,1,-5,4])

위 코드에서 j를 반복할 때, 합을 누적하면서 비교하면 시간복잡도 O(n^2)로 개선할 수 있다.

var maxSubArray3 = function(nums) {
  if (nums=== null || nums.length === 0) return 0

  let maxSum = nums[0]

  for (let i = 0; i < nums.length; i++) {
    let currSum = 0;
    for (let j = i; j < nums.length; j++) {
      currSum += nums[j];
      maxSum = Math.max(maxSum, currSum)
    }
  }
  return maxSum
}

DP (Dynamic Programming) 접근

dp[i]는 각 i까지의 누적 합이다. 즉, 현재 인덱스의 누적합은 바로 이전 인덱스 dp[i-1]와 현재 nums[i] 값의 합이다. 하지만 dp[i-1] + nums[i]가 현재 nums[i]보다 작다면 nums[i]를 dp[i]에 담는다. (부분 배열의 시작 인덱스를 변경함)

DP는 시간,공간 복잡도 O(n)를 가진다.

var maxSubArray = function(nums) {
  if (nums=== null || nums.length === 0) return 0

  let dp = new Array(nums.length).fill(0);
  dp[0] = nums[0]

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

dp 배열은 [ -2, 1, -2, 4, 3, 5, 6, 1, 5]로 Math.max(dp[i-1] + nums[i], nums[i])공식을 적용하면, 3번째 인덱스와 7번째 인덱스에서 nums[i]를 대입하게 된다. 즉, 인덱스 3~6까지 [4,-1,2,1]의 합인 6이 가장 큰 부분배열의 합이 된다.

Kadane's 알고리즘

DP 접근법와 동일한 공식을 가지고 n만큼의 배열을 만드는 대신 변수에 담아 maxSum을 변경하는 식으로 공간복잡도를 O(1)의 상수로 개선할 수 있다. 제안한 이의 이름을 붙여 카데인의 알고리즘(1984)이라고 한다.

var maxSubArray = function(nums) {
  let currSum = nums[0];
  let maxSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currSum = Math.max(currSum + nums[i], nums[i]);
    maxSum = Math.max(currSum, maxSum)
    console.log(currSum, maxSum)
  }
  return maxSum;
};

출처

• Maximum_subarray_problem | wiki
• from-brute-force-to-dp-to-kadanes-alogrithm | leetcode