[leetcode 2024/02/27] 53. Maximum Subarray

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

Maximum Subarray - LeetCode

 

1. 접근 방법

우선, nums 리스트의 앞과 뒤에서 양수가 처음 나오는 index를 찾아주었다.

 

이를 통해, 리스트의 앞과 뒤에서 모두, 양수로 값을 시작하도록 설정해 주었다. 앞 뒤로 음수들을 잘라줘서, 불필요한 계산을 하지 않도록 하였다.

이후, 값을 앞에서부터 하나씩 읽어주었다.

 

[ -1, -2, -2, -4, 1, 2, 3, -1, -2, -4] #로 구성되어 있을 경우,
[1, 2, 3] #만 찾아낼 수 있도록 하였다.

 

현재까지 저장된 값 + 새로 저장될 값이 음수라면, 지금까지 읽어온 값들을 포함시키지 않기로 결정하고 다시 

0부터 값을 저장하기 시작하였다.

즉,

[1, -3, 2, 4] #로 있다면, 1 + -3 을 하게 된다면 -2로 음수가 된다. 이때, 1, -3 을 버리기로 하고
[2, 4] #부터 값을 읽기 시작한다.

 

 

예외로 처리해야할 부분이 있었다. 바로, 0과 음수만으로만 이루어진 리스트일 때이다.

그 때에는, max(리스트)를 통해서 값을 바로 출력해주면 된다. 음수만으로 이루어질 경우, 더하면 더할수록 값이 - 되기 때문이다.

[-1, -2, -4] # 로 음수로만 구성된 리스트의 경우, max(list) 의 값인 -1이 제일 큰 값이 될 것이다.

 

따라서, 앞과 뒤에서 양수가 처음 나오는 index를 찾아줄 때, index를 찾지 못했다면, -1을 반환해주어, list가 음수와 0으로만 구성되어 있음을 알아낼 수 있었다.

 

2. 코드

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

        def cut_last(nums):
            for i in range(len(nums) - 1, -1, -1):
                if nums[i] > 0:
                    return i

            return -1

        def get_max_subarray(front_i, last_i):
            if front_i == -1 and last_i == -1:
                return max(nums)

            total = 0
            sum_total = []
            for num in nums[front_i:last_i + 1]:
                if total + num > 0:
                    total += num
                    sum_total.append(total)

                else:
                    total = 0

            return max(sum_total)

        front_i = cut_first(nums)
        last_i = cut_last(nums)
        return get_max_subarray(front_i, last_i)