LeetCode - 53. Maximum Subarray (Python)

Medium, 최대연속부분배열

RunTime : 560 ms / Memory : 30.96 MB

문제

Given an integer array nums, find the subarray with the largest sum, and return its sum.

풀이

• 최대연속부분배열을 찾을 땐 분할 정복 or DP의 풀이를 생각할 수 있다.
• 분할 정복은 O(nlogn)의 시간복잡도를 가지고 DP는 O(n)의 시간복잡도를 가진다.
• DP로 풀었다. 분할 정복을 할 줄 모름...

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

        for num in nums[1:]:
            psum = max(psum + num, num)
            maxSum = max(psum, maxSum)
        return maxSum