53. Maximum Subarray

연속된 서브 어레이 중에서 합이 가장 큰 서브 어레이를 구하고 그 합을 리턴한다.

 

solution 1.

왼쪽, 오른쪽 포인터를 이용해서 풀이.

왼쪽, 오른쪽 포인터를 움직이기 위해서는 다음 숫자가 음수여야하고 그 다음, 그 다음,... 등등 과 합했을 때 더 클 수 있다는 것을 증명해야 한다. 그리고 이는 정렬된 상태에서 하는 것이 현명하다. 하지만 그렇게 되어있지 않기 때문에 이는 쉽지 않다.

pass

 

solution 2.

메모제이션 기법.

차례로 누적합을 계산해나가되, 음수가 되는 누적합은 버리고 다시 차례로 누적합을 진행한다.

 

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

input을 활용하여 공간을 활용을 높였다.