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.

https://leetcode.com/problems/maximum-subarray/

접근

#DP
연속된 배열 중 가장 합이 큰 부분 배열을 찾아내는 문제.
이전 값을 참조해야 하므로 dp로 접근했다.
i번째의 배열에서 부분 합의 최댓값은 두 가지 경우의 수가 있다. 첫 번째는 이전 배열의 합에서 자신의 값을 더한 것, 다른 하나는 이전 값을 무시하고 자신이 새 부분 배열의 첫 값이 되는 것. 선택하는 것은 값이 가장 큰 경우이며, 이를 정리하면 점화식은 다음과 같다.

DP[i] = max(DP[i-1]+nums[i], nums[i])
answer = max(answer,dp[i])

i번째 배열에서의 최대 부분합을 담은 dp이므로, for문을 돌면서 answer의 값을 갱신시켜준다. answer에는 최종적으로 가장 큰 부분 배열의 합이 담기게 된다.

코드

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

효율성

Runtime: 2138 ms, faster than 5.64% of Python3 online submissions for Maximum Subarray.
Memory Usage: 28.6 MB, less than 10.53% of Python3 online submissions for Maximum Subarray.