53. Maximum Subarray

LeetCode Link (opens in a new tab)

dynamic programming

Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example cases

Example 1:

• 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.

Example 2:

• Input: nums = [1]
• Output: 1
• Explanation: The subarray [1] has the largest sum 1.

Example 3:

• Input: nums = [5,4,-1,7,8]
• Output: 23
• Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints

• ${1 <=}$ nums.length ${<= 10^5}$
• ${-10^4 <=}$ nums[i] ${<= 10^4}$

Approach

주어진 숫자 배열에서 가장 큰 합을 가지는 subarray를 찾아 그 합을 반환하는 문제이다.
당연하겠지만 모든 subarray를 탐색하여 합을 구하는 brute-force로 접근할 수 있다. 하지만 dynamic programming을 이용하면 오히려 간단히 해결할 수 있다
여기서 중요한건 가장 값이 큰 subarray를 찾아 반환하라는 것이라 합만 구해서 출력하면 된다는 것이다.
예제 1을 통해 어떻게 DP로 해결할 수 있는지 살펴보자.

• [-2,1,-3,4,-1,2,1,-5,4]

dp변수를 첫 번째 원소로 초기화하고, max변수에도 첫 번째 원소를 할당한다.
다음 숫자를 nums[i]라 할 때, nums[i]와 dp를 더한 값이 nums[i]보다 작으면 (dp + nums[i] < nums[i]) dp를 nums[i]로 초기화한다. 아니라면 dp에 nums[i]를 더한다.
이렇게 진행할 수 있는 이유는 이전에 계산된 합이 (dp) 현재 값보다 작으면 이전 합은 의미가 없고, 현재 값으로 시작하는것이 옳은 판단이기 때문이다
이렇게 dp를 갱신하고 나면 max와 dp를 비교하여 더 큰 값을 max에 할당한다.
배열을 한번만 순회하면 되기 때문에 $O(n)$의 시간복잡도로 해결할 수 있다

Solution Code

var maxSubArray = function(nums) {
    let dp = nums[0]
    let max = nums[0]
 
    for (let i = 1; i < nums.length; i += 1) {
        if (dp + nums[i] < nums[i]) {
            dp = nums[i]
        } else {
            dp += nums[i]
        }
        max = Math.max(max, dp)
    }
 
    return max
};

Complexity

• time complexity : $O(n)$
• space complexity : $O(1)$