53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/?envType=featured-list&envId=top-google-questions?envType=featured-list&envId=top-google-questions

input :

• nums

output :

• 연결된 부분수열의 합이 최대가 되는 수열의 합을 출력하시오.

조건 :

• 1 <= nums.length <= 10^5

---

Solution explain : Solution1

idea

• 1차원 배열의 누적합을 구하는 방식을 사용하자.

주의

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [-float("inf")] * len(nums)
        dp[0] = nums[0]
        ret = nums[0]

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