리트코드-53. 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.

A subarray is a contiguous part of an array.

풀이

주어진 배열 중 합이 가장 큰 서브배열의 합을 구하는 문제다. 이를 풀기 위해서 다음과 같은 생각을 했다.

• 서브 배열의 합만 구하면 되기 때문에, 인덱스 0부터 n까지 누적합을 차례대로 구하는 방식인 DP를 응용하기로 했다.
• 최대값을 구하는 것이므로 이전 인덱스의 누적합이 음수이면 더하지 않기로 했다.

코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        answer = nums[0]
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i-1])
            answer = max(nums[i], answer)
        return answer