📃 문제 설명

Maximum Subarray

[문제 출처 : LeetCode]

👨‍💻 해결 방법

원소들의 합이 가장 큰 Subarray를 구하는 문제.
DP로 풀었다.

dp 배열을 만들어서 Subarray의 합을 저장할건데,
이때, dp[i]의 의미는 nums[0]부터 nums[i] 까지의 Subarray 중 최댓값이다.

이를 위해 다음과 같은 점화식을 세웠다.
dp[i] = max(dp[i-1]+nums[i], nums[i])

모든 Loop를 끝내면,
dp 배열 중 가장 큰 값을 반환하면 된다.
끗 !

👨‍💻 소스 코드

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

        for n in nums[1:]:
            dp.append(max(dp[-1] + n, n))

        return max(dp)