LeetCode: Maximum Subarray

 

쉽지 않은 문제였다. 

 

이전에 jump game2 문제와 비슷한 문제였다. 

 

흐름은 다음과 같다. 

 

 

• 현재까지의 부분합을 유지하면서,
• 음수로 인해 흐름이 나빠지면 과감하게 끊고 다시 시작
• 가장 큰 값을 max_sum에 저장

작동방식은 정말 단순한데 이 안에서 현재 값과 현재에서 다음 값을 합친 값과 비교하여 

둘 중 큰 값을 current_sum으로 저장해놓는다.

이후 가장 큰 값(max_sum)과 비교하여 더 큰 값을 max_sum에 저장해놓는다. 

 

지금까지 합해왔던 수열을 버리고 새로운 수열을 탐색하는 조건은 지금까지의 합보다 새로운 수가 더 클때이다. 

 

 

---

구현코드

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        current_sum = max_sum = nums[0]  # 첫 원소로 초기화

        for num in nums[1:]:
            current_sum = max(num, current_sum + num)  # 현재값을 포함할지 새로 시작할지 결정
            max_sum = max(max_sum, current_sum)        # 최대값 갱신

        return max_sum