53. Maximum Subarray (Medium) [Python]

문제

 

생각 방식

Brute force로 충분히 풀 수 있는 문제다

하지만 코딩 테스트 특성상 그리고 문제의 난이도를 보아하니 brute force로 풀면 런타임 에러가 뜰게 분명하다

그렇다면 Greedy 알고리즘을 사용해 본다

 

일단 마지막으로 준 테스트 케이스가 제일 보기 편하지만 최댓값은 결국 모든 수를 더한 거라 별 의미가 없어 보여 [5,4,-10,7,8,10]를 테스트 케이스로 만들어 봤다.

조금만 풀어보면 [7,8,10]이 maxSubArray라는 것을 우리는 알 수 있다.

 

대충 글로 먼저 코드를 작성했다

maxSubVal = 0
current = 0

loop through every numbers in nums array:

	if current is less than 0, then reset current as 0. greedy

	add numbers from nums array to current

	compare with maxSubVal with current and find the maximum value from those two

return the maximum value that we found

 

일어난 문제

일단 current라는 변수를 0으로 설정해 주고, maxSub라는 변수도 0으로 설정해 줬다

근데 nums가 다 음수일 때 테스트 케이스를 통과하지 못했다.

 

예를 들면 [-2]가 nums라면, loop을 돌릴 때 current는 -2가 될 것이고, maxSubVal은 0이니까, 결과로 0이 나오게 된다

근데 0이라는 숫자는 애초에 nums 안에 존재하지 않기 때문에 에러가 나는 것이다

그래서 maxSubVal를 nums[0]으로 지정해 줘서 해결을 해봤다

 

💻 마지막으로 수정 후 제출한 코드

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub = nums[0]
        current = 0
        for num in nums:
            if current < 0:
                current = 0
            current += num
            maxSub = max(maxSub, current)
        return maxSub

 

 

그림으로 설명

결과