[알고리즘] 최대 서브 배열

최대 서브 배열

내 풀이

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

        return max(dp)

dp 배열을 만들고, 상향식으로 풀었다. dp[i] = i까지 고려했을 때 가장 큰 sum이다. 만약 이전의 것이 음수이면 굳이 dp[i-1]을 더할 필요가 없다.