(leetcode 문제 풀이) 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.
 
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:
Input: nums = [1]
Output: 1

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
 
Constraints:
1. 1 <= nums.length <= 3 * 10^4
2. -10^5 <= nums[i] <= 10^5
 
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
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = nums
        for i in range(1, len(nums)):
            result[i] = max(result[i - 1] + nums[i], nums[i])
        
        return max(result)

# 방법 2
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i - 1] > 0: # 이전의 숫자가 양수일 때만 더하기
                nums[i] += nums[i - 1]
        
        return max(nums)

해당 문제는 DP(다이나믹 프로그래밍)을 사용하여 해결해야 한다. 처음엔 brute force로 풀었다가 시간 초과 오류가 발생한 점을 보아 DP가 필요할 듯 하다.

DP는 각 인덱스 위치에 해당 인덱스까지의 최댓값을 저장하고 최종적으로 max값을 출력하면 된다. 예를 들면 아래와 같다.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

첫 번째 코드의 result 변수의 인덱스는 최댓값을 가리킨다. nums[0] = -2, nums[1] = 1 로 둘을 더한 값은 -1, 더하지 않고 nums 인덱스 그대로 가는 것은 1로 후자가 더 크기 때문에 result[1] = 1 이 된다.

result = [-2, 1, ...]

이후 result[1] + nums[2] = -2, nums[2] = -3 이므로 전자가 더 크기 때문에 result[2] = -2 가 된다.

result = [-2, 1, -2, ...]

이후 result[2] + nums[3] = 2, nums[3] = 4 이므로 후자가 더 크기 때문에 result[3] = 4 가 된다.

result = [-2, 1, -2, 4, ...]

이렇게 result의 각 인덱스는 해당 인덱스까지 진행했을 때 나온 최댓값을 보유하고 있는 것이다.

두 번째 코드 역시 로직은 동일하지만 좀 더 직관적일 수 있다. 새로운 result 변수 선언 대신 nums에서 진행하되, 이전의 숫자가 양수일 때만 더하는 것이다. 최댓값을 찾는 문제이기 때문에 이전의 수가 음수이면 더하지 않는 것이 필요할 것이다.

DP 문제는 얼핏 봐서 바로 떠올려지지 않는다... 솔직히 처음에는 brute force 등으로 접근했다가 효율성 문제에서 막힌다면 다른 방법을 생각하고, 최댓값을 구하는 데 누적이 필요하다면 DP를 고려해볼 수 있겠다.