leetcode - 30-Day LeetCoding Challenge - 3. Maximum Subarray

문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3285/

정수배열 nums가 있습니다. 인접한 숫자들로 부분배열을 만들었을 때, 이 부분 배열들의 합 중 가장 큰 합을 구하는 문제입니다.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

 

우선 brute force 하게 구현해 볼 수 있습니다. 모든 부분배열의 합 중 가장 큰 값을 찾으면 됩니다.

class Solution:
    def maxSubArray(self, nums):
        result = nums[0]
        len_num = len(nums)
        for i in range(len_num):
            tmp = nums[i]
            result = max(tmp, result)
            for j in range(i+1, len_num):
                tmp += nums[j]
                result = max(tmp, result)
        return result

첫번째 loop

-2
-2+1
-2+1-3
-2+1-3+4
...

두번째 loop

1
1-3
1-3+4
1-3+4-1
...

결국 답이 나오기는 합니다. 하지만 테스트 케이스가 길어 지면 시간 초과로 결국 실패하게 됩니다. 테스트 케이스 202개중 201번째에서 시간 초과가 발생하네요. 반복문이 이중이라 시간복잡도는 O(n^2)입니다.

Kadane's Algorithm

Maximum Subarray문제를 풀기 위해서는 결국 이 알고리즘을 사용하게 됩니다.

wiki(https://en.wikipedia.org/wiki/Maximum_subarray_problem)등에 설명이 나와있긴 하지만 저도 아직 완전히 이해는 안되고 설명하기도 좀 어렵네요. 좀 더 이해하게 되면 다시 정리해 봐야 겠습니다.

코드는 다음과 같습니다.

class Solution:
    def maxSubArray(self, nums):
        tmp = nums[0]
        result = nums[0]

        for num in nums[1:]:
            tmp = max(tmp + num, num)
            result = max(tmp, result)

        return result