[알고리즘] Leetcode Maximum subarray 파이썬 풀이

문제 링크

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

풀이 방법

동적 프로그래밍 문제.

nums와 같은 값을 가지는 dp 배열을 생성한다.

이때, dp[i]의 의미는 nums[0]부터 nums[i] 까지의 subarray 중 최댓값이다.

nums[i] 원소에 대해 우리는 2가지 행동을 취할 수 있다.

1. nums[i-1] 원소와 nums[i] 원소를 더 하는 것

2. nums[i]를 시작으로 새로운 subarray를 시작하는 것

이걸 그대로 점화식으로 나타낸다면

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

가 된다.

모든 루프를 끝내면,

dp 배열 중 가장 큰 값을 리턴.

코드

class Solution(object):
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    dp = [num for num in nums]
    for i in range(1, len(nums)):
      dp[i] = max(dp[i-1]+nums[i], nums[i])

    return max(dp)