[코테] 리트코드 다이나믹 프로그래밍 53. Maximum Subarray

53. Maximum Subarray

문제 링크

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

문제 설명

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

제한 사항

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

입출력 예 #1

1. Input : nums = [-2,1,-3,4,-1,2,1,-5,4]
2. Output : 1
3. Explanation : The subarray [4,-1,2,1] has the largest sum 6.

입출력 예 #2

1. Input : nums = [1]
2. Output : 1
3. Explanation : The subarray [1] has the largest sum 1.

입출력 예 #3

1. Input : nums = [5,4,-1,7,8]
2. Output : 23
3. Explanation : The subarray [5,4,-1,7,8] has the largest sum 23.

문제 풀이

이전의 값이 0 보다 클때만 합을 구하여 최대인 값을 출력한다.

1. 메모이제이션
2. 카데인 알고리즘

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += nums[i-1] if nums[i - 1] > 0 else 0
        return max(nums)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best_sum = -sys.maxsize
        current_sum = 0
        for num in nums:
            current_sum = max(num, current_sum + num)
            best_sum = max(best_sum, current_sum)

        return best_sum