[Python] MaximumSubarray

Easy 난이도 Acceptence 48%의 문제

 

주어진 리스트에서의 subarray중 합이 최대인 원소의 집합을 구하여

최댓값을 반환하는 문제

 

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Kadane's Algorithm DP
        curSum = maxSum = nums[0]
        
        for i, num in enumerate(nums[1:]):
            curSum = max(nums[i+1], nums[i+1] + curSum)
            maxSum = max(curSum, maxSum)

        return maxSum