[LeetCode] 53. Maximum Subarray (JS)

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

Maximum Subarray - LeetCode

핵심 아이디어

• Sliding Window
  • 지금까지 구했던 prefix sum이 음수이면 더하는게 의미가 없으므로 값을 누적할 때 버린다

 

복잡도

• 시간 복잡도: O(n)
  
  • 배열 1회 순회
• 공간 복잡도: O(1)
  
  • 저장하는 변수 외에 추가적으로 사용하는 메모리 없음

 

설명

알고리즘을 개선해 가는 해설이 재미있다.

1. 브루트 포스로 가능한 모든 subarray sum을 구하면 i, j 순회하는 데 n^2 * i~j sum 구하는 데 n = O(n^3)의 시간이 걸린다

2. 연속된 배열에서 구하는 것이므로 sum 구하는 과정은 앞의 계산 결과(currentSum)을 활용하면 O(n^2)로 최적화할 수 있다

3. 누적된 sum이 음수라면 다음 값을 더하는게 의미가 없으므로 그만 순회하고 다음 값으로 넘어가면 O(n)으로 최적화할 수 있다

이 문제에서 sliding window를 떠올리는 단서는 contiguous subarray, largest sum이 아닐까 싶다

 

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let currentSum = 0;
    let maxSum = nums[0];
    
    for (num of nums) {
        if(currentSum < 0) {
            currentSum = 0;
        }
        currentSum += num;
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};

 

유튜브 NeetCode 해설 영상