Leetcode 53. Maximum Subarray

## 문제이해

전체 배열중에 부분 배열이 최댓값인 배열을 찾고, 최댓값을 출력하는 문제 였다.

 

## 생각해 본 방법

처음에는 left, right 포인터를 사용해서 푸는 문제인가 했는데, 전형적인 dp 문제였다.

예시에 -2, 1, -3, 4, -1, 2, 1, -5, 4 가 있다면
dp 배열을 만들어주고 현재 인덱스에 최대 합을 넣어주면된다
idx = 0 일때는 -2 만 있으므로, 최대값을 넣어주고
그 이후에는 dp[i-1]의 최댓값과 현재값을 더한게 큰지, 아니면 현재 값을 넣는게 큰지 비교해서 넣으면 된다.

## Try 1. 성공

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp 는 현재 인덱스에서 가장 최대의 값을 넣는다.
        dp = [0] * len(nums)
        for i in range(len(nums)):
            if i == 0:
                # 0 의 값 초기화
                dp[i] = nums[i]
            else:
                # 이전값과 더해서 최댓값이 나오면 이전값+현재값을, 아니면 현재값을 넣는다.
                dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)