32. Maximum Subarray

  • by

1. 문제

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


2. 답안

1. 내가 생각한 잔디

class Solution:
    def maxSubArray(self, nums: List(int)) -> int:
        dp = (i for i in nums)  # nums(0) ~ nums(i)번째 숫지까지의 합은 dp(i) 
        
        for i in range(1, len(nums)):
            dp(i) = max(nums(i), dp(i-1) + nums(i))
        
        return max(dp)

2. YouTube 풀

class Solution:
    def maxSubArray(self, nums: List(int)) -> int:
        maxSub = nums(0)
        curSum = 0

        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSub = max(maxSub, curSum)
            
        return maxSub

예 1을 예로 들어 보겠습니다.

(-2, 1, -3, 4, -1, 2, 1, -5, 4)를 앞에서 보자. -2부터 시작한다.

인기글

(ic)(-2) + 1 = -1(/ic) : 음수는 최대값을 보장하지 않습니다.

버린다.

(ic)1 + (-3) = -2(/ic) : 마찬가지로 음수가 나왔으므로 저장하지 않고 버린다.

(ic)4 + (-1) = 3(/ic) : 양수가 나왔다.

최대 합계가 나올 수 있다.

그래서 저장합니다.

그렇게 계속 4+(-1)+2+1까지 진행하면 6이 나온다.

대답이 나왔지만 일단 계속 해보자.

(ic)6 + (-5) = 1(/ic)

(ic)1 + 4 = 5(/ic)

결국 전에 구한 6이 Maximum Subarray다.

negative prefix가 나오면 삭제하고 sliding window처럼 진행한다.

linear time algorithm이기 때문에 시간의 복잡성은 O(n)입니다.

출처: 1번 코드

출처: YouTube

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

Maximum Subarray – LeetCode

Can you solve this real interview question? Maximum Subarray – Given an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = (-2,1,-3,4,-1 ,2,1,-5,4) Output: 6 Explanation: The subarray (4,-1,2,1) has t

leetcode.com