53. Maximum Subarray

Description

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

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⁵
• -10⁴ <= nums[i] <= 10⁴

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.

Submitted Code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = 0              # 현재까지 누적값
        max_sum = float('-inf')   # 최대 누적값

        for n in nums:
            curr_sum = max(n, (curr_sum + n)) # 이전까지의 합을 계속 잇거나 여기서 새로 시작
            max_sum = max(curr_sum, max_sum)

        return max_sum

Runtime: 35 ms | Beats 62.61%
Memory: 31.24 MB | Beats 96.33%

배열을 한 번만 순회하기 때문에 𝑂(𝑛) 시간 안에 풀 수 있는 방법이다.

Other Solutions

1st

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:            
        res = nums[0]
        total = 0

        for n in nums:
            if total < 0:
                total = 0

            total += n
            res = max(res, total)
        
        return res

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

이전까지의 합이 음수이면 현재 숫자에 붙일 경우 무조건 더 작은 숫자가 되기 때문에 새로 시작할 수 있다.

2nd

from math import inf

class Solution:
    def maxSubArray(self, nums):
        def maxSubArray(A, L, R):
            if L > R: return -inf
            mid, left_sum, right_sum, cur_sum = (L + R)
            for i in range(mid-1, L-1, -1):
                left_sum = max(left_sum, cur_sum := cur_sum + A[i])
            cur_sum = 0
            for i in range(mid+1, R+1):
                right_sum = max(right_sum, cur_sum := cur_sum + A[i])

            # 왼쪽, 오른쪽, 가운데 걸치는 범위 중 최대값 찾기
            return max(maxSubArray(A, L, mid-1), maxSubArray(A, mid+1, R), left_sum + A[mid] + right_sum)
        return maxSubArray(nums, 0, len(nums)-1)

time complexity: 𝑂(𝑛log𝑛)
space complexity: 𝑂(1)

분할 정복을 사용한 방법으로, 최대 subarray은 왼쪽 절반, 오른쪽 절반 또는 중앙을 가로지르는 범위 3개 중 하나에 포함되어 있다는 것이 포인트이다.