[leetcode] 53. Maximum Subarray 파이썬 코드

배열이 주어졌을 때 이 배열의 subarray 중에서 가장 큰 합을 가지는 subarray의 합을 구하는 문제다. 

 

[8, -1, -1, -1, -1] 이런 배열도 있을 수 있겠고, 문제에서 예제로 주어진 건 3가지 배열이다. 

nums = [-2,1,-3,4,-1,2,1,-5,4]
nums = [1]
nums = [5,4,-1,7,8]

 

그래서 1개씩만 element를 볼 때, 2개, 3개, ..., len(nums)개를 한 꺼번에 볼 때 합을 구하도록 만들었다.

 

maximum = nums[0]

for k in range(1, len(nums)+1): # k = 1, 2, 3, 4, 5
    for i in range(len(nums)+1-k): # 5 + 1 - 1 = 5 # i = 0, 1, 2, 3, 4
        temp = sum(nums[i:i+k])
        if temp > maximum:
            maximum = temp

 

그런데 시간 초과가 났다. 배열의 길이가 10^5 일 수도 있는데 for 문을 2번을 돌렸으니 그럴 만도 했다.

 

다른 사람은 어떻게 풀었을까 찾아보니까 '오...' 

 

[-2,1,-3,4,-1,2,1,-5,4] 이런 배열이 있다고 하자. 최대 합을 일단 0th 인덱스인 -2로 둔다. maxSum = nums[0]

하나씩 더해나갈껀데 1을 더하면 -1이다. 이걸 curSum이라고 하자. 그러면 maxSum과 curSum을 비교를 해서 큰 값을 maxSum에 넣어준다. maxSum = max(maxSum, curSum)

그런데 사실상 음수는 최대 합을 만드는데 도움이 되지 않는다. 그래서 음수는 버리도록 하자. 음수를 버리는 코드를 for문을 돌릴 때 맨 처음에 넣어준다. curSum = 0

curSum = 0 이 코드의 의미는 subArray 시작 포인터를 그 다음으로 옮긴다는 뜻도 된다. (곰곰이 생각해보니 이 점이 아주 놀라웠다.)

 

그래서 전체 코드는 이렇게 간결하고 아름답게 나온다. 이 코드의 시간 복잡도는 O(n)이다.

 

class Solution(object):
    def maxSubArray(self, nums):
        maxSum = nums[0]
        curSum = 0

        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSum = max(maxSum, curSum)
        return maxSum

 

 

참고

https://youtu.be/5WZl3MMT0Eg?si=TaI-_YBydGBN862R