[LeetCode] 53 | Maximum Subarray

53 | Maximum Subarray
https://leetcode.com/problems/maximum-subarray/

 

 

 

작성 코드

 

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

 

 

• i, j 로 돌면서 nums[i:j+1]이 prev_sum 이 prev_sum 보다 클 경우 prev_sum 갱신
• 시간 초과 발생

 

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        prev_sum, max_right, max_left = nums[0], 0, 0
        
        for right in range(0, len(nums)):
            nums_sum = sum(nums[:right + 1])
            if nums_sum > prev_sum:
                prev_sum = nums_sum
                max_right = right
                
        for left in range(0, max_right + 1):
            nums_sum = sum(nums[left : max_right + 1])
            if nums_sum > prev_sum:
                prev_sum = nums_sum
                max_left = left
                
        return max(prev_sum, max(nums))

 

 

 

• right 와 left 각각 큰 값을 갱신해야겠다고 생각했으나 잘못된 접근 방식

 

 

 

이상 코드

 

카데인 알고리즘

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i] = max(nums[i], nums[i-1] + nums[i])
        return max(nums)
        
# [출처] https://leetcode.com/problems/maximum-subarray/discuss/20396/Easy-Python-Way

 

 

• nums[i] 와 nums[i-1] + nums[i] 중 큰 값을 nums[i]에 대입
• 간결하지만, input 값을 수정하면 좋지 않다는 의견이 있었음

 

정석적인 DP 방법은 

 

https://leetcode.com/problems/maximum-subarray/discuss/1595195/C%2B%2BPython-7-Simple-Solutions-w-Explanation-or-Brute-Force-%2B-DP-%2B-Kadane-%2B-Divide-and-Conquer

✅ [C++/Python] 7 Simple Solutions w/ Explanation | Brute-Force + DP + Kadane + Divide & Conquer - LeetCode Discuss

 

에 잘 설명되어있음, 추후 추가 예정.