leetcode.com 53. Maximum Subarray

 문제 링크: https://leetcode.com/problems/maximum-subarray/description/

파이썬 소스: https://bit.ly/4caMLWo

 

 우선 nums와 길이가 같은 dp 리스트를 하나 만들어 줍니다. 이후에 설명하겠지만, max() 함수를 사용해서, dp 리스트에 값을 어싸인할 것이므로, 모두 최소값(이문제에서는 10**4 -1)으로 초기화 해줍니다.

음수와 양수가 서로 섞여 있는 상태에서 가장큰 부분합을 가지는 subarray의 합을 찾는 문제입니다. 문제의 초점을 헷갈릴 수 있어서, 다시한번 정리하면, Subarrary를 찾는 문제가 아니라, 가장 큰 부분합을 찾는 문제입니다.

Subarray가 가장 큰 부분합을 가지려면, 가장 작은 subarray인 길이가 2인 subarray에 대해서 먼저 알아보겠습니다.

 여기서, 나를 최대합이 되고 싶은 dp 리스트에 있는 하나의 원소라고 가정합니다.

그러면, dp[0]인 나는 nums[0] 이 됩니다. 나의 왼쪽에 아무도 없기 때문입니다.

이제 나는 dp[1] 입니다. 나의 왼쪽에 있는 친구를 더해서, 나는 최대합이 되고 싶습니다.

dp[1] = max(nums[1], dp[0] + nums[1])

 

dp[1]에 대해서 코드로 작성해 보면 위와 같습니다. 이 코드를 인덱스 i 에 대해서 작성해보겠습니다.

for i in range(1, len(nums)):     dp[i] = max(nums[i], dp[i-1] + nums[i])

 

이 문제를 풀 때, 주의 할 점은, 최대 합을 구하는 것이지, 최대 합을 가지는 구간을 구하는 문제가 아닙니다.

즉, dp 리스트에 있는 각 아이템들이, 나의 왼쪽을 더할 것인지 아닌지를 판단하면, 자연스럽게 최대합을 구할 수 있습니다.

 

from typing import List class Solution:     def maxSubArray(self, nums: List[int]) -> int:         dp = [-1 * (10 ** 9) -1] * 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)

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul