[LeetCode]Maximum Subarray

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

Maximum Subarray - LeetCode

 

문제 분석

주어진 nums 리스트에서 숫자들의 합이 최대가 되는 subarray를 구하는 문제입니다. 가장 큰 연속된 부분 배열의 합을 구합니다.

 

처음 시도한 답안

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]

        for idx in range(1, len(nums)):
            # 현재 값이 더 크다면 이전까지의 subarray를 포기하고 새롭게 시작
            # 현재 값이 이전+현재 보다 작다면 subarray를 확장함
            if nums[idx-1] + nums[idx] > nums[idx]:
                # nums 배열의 값을 바꾸어주는 것으로 subarray를 기록하는 효과를 얻음
                # 현재까지의 subarray의 sum된 값을 기록하는 것
                nums[idx] = nums[idx-1] + nums[idx]
            
            # 위 조건을 수행후 max_sum 최신화
            max_sum = max(max_sum, nums[idx])

        return max_sum

접근 방법

1. 처음 숫자를 최댓값으로 설정합니다.
2. 두번째 요소부터 반복을 순회합니다.
3. 현재 반복에서 등장한 값이 이전까지의 subarray(이 값에는 이전까지의 최댓값이 담겨져 있음) 보다 크다면
   이전까지의 subarray를 버리고 새롭게 시작합니다.
4. 아니라면 nums 배열의 값을 바꾸면서, subarray의 sum값을 기록하도록 합니다.
5. 그 이후 max_sum 값을 갱신합니다.

반복을 순회하면서 nums 배열에 subarray를 선택한 경우에 sum 값을 누적해서 기록해주면서 max_sum을 구하는 방법입니다. 예시는 다음과 같습니다.

 

반복을 순회하기 전 -> nums = [-2, 1, -3, 4, -1, 2 ,1, -5, 4]

반복을 모두 순회하고 난 뒤 -> nums = [-2, 1, -2, 4, 3, 5, 6, 1, 5]

 

 

 

nums[3] 요소를 보면 전과 후 모두 4로 동일합니다. 그 이유는 nums[0~2] 까지의 요소들의 합보다 nums[3]에서 등장한 요소 자체가 더 큰 값을 가지기 때문입니다. 따라서 이전까지의 합을 무시하고 nums 배열의 값을 조작하지 않도록 하여 subarray를 새롭게 선택하는 효과를 가지게 합니다. 

 

이런식으로 반복을 완료하면 최대 값을 구할 수 있습니다.

 

두번째로 시도한 답안

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = current_max_subarray = nums[0]

        for num in nums[1:]:    
            # 현재 등장한 숫자와 현재 + 이전까지의 누적 합계를 더한것중 큰것을 선택
            current_max_subarray = max(num, num + current_max_subarray)
            # 최대 합계를 갱신
            max_sum = max(max_sum, current_max_subarray)

        return max_sum

접근 방법

1. 기본적인 방식은 첫번째와 동일합니다.
2. 조건문을 단순화하고, current_max_subarray 변수를 통해 조금 더 직관적이게 했습니다.