[카데인 Kadane] 53. Maximum Subarray

53. Maximum Subarray

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        # window = l-r
        # l는 1개씩 증가하는데, 
        # l부터 len(nums) 까지, max_sum 계속 구함
        max_sum = -float("inf")
        for l in range(len(nums)):
            # if nums[l] <0:
            #     continue
            sum = 0
            for r in range(l, len(nums)):
                sum += nums[r]
                max_sum = max(max_sum, sum)   
        
        return max_sum

 

Time Limit Exceeded

 

https://youtu.be/5WZl3MMT0Eg?si=F16OBsmPYHPefkwv

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 가장 큰 연속 부분 배열의 합을 찾는 
        # Kadane's Algorithm을 구현
        # 최대값 maxSub
        maxSub = nums[0] # 배열의 첫 번째 값이 최소한 초기 최대값으로 간주
        
        # 현재 연속된 부분 배열의 합을 저장, 
        # 현재 고려 중인 부분 배열의 누적 합
        curSum = 0 

        for n in nums:
            if curSum <0:
                """
                만약 curSum이 음수가 되면, 이를 0으로 리셋
                이유: 음수인 부분 배열은 
                    다음 값을 더할 때 이득을 주지 않기 때문
                    음수인 합에 숫자를 더하면 값이 더 작아질 수 있음
                    따라서, 새로 시작하는 것이 
                        더 큰 합을 만들 가능성이 높음
                """                
                curSum = 0
            curSum += n # 현재 연속된 부분 배열의 합
            maxSub = max(maxSub, curSum)

        return maxSub

 

최종 코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 연속 부분 배열의 최대 합 => 카데인 kadane 알고리즘
        maxSum = nums[0]
        curSum = 0

        for n in nums:
            curSum = max(curSum, 0) # 누적된 이전 Sum 값이 마이너스이면, 무시, 0으로 초기화
            curSum += n

            maxSum = max(maxSum, curSum)
        return maxSum