[Python] Leetcode 53. Maximum Subarray (Medium)

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

Maximum Subarray - LeetCode

 

연속 부분 수열의 최대합(한국어로 맞는지 모르겠습니다)을 구하는 정말 유명한 DP 문제입니다.

문제를 볼 때마다 매번 10초 정도 LCS와 헷갈립니다. 완전히 다른 알고리즘이라 금방 깨닫긴 하지만, 아마 입력의 형태가 비슷해서 그런것 같습니다. 

저만 그럴수도 있구요.

 

아이디어는 이렇습니다. 배열 nums가 주어졌다고 할때, 

어떤 위치 i 에서 끝나는 부분수열의 최대합은 두가지 경우입니다.

i-1에서 끝나는 부분수열의 최대합이 양수라서 그 값을 더하거나, 버리고 자기 자신만 취하거나

 

배열을 만들어서 각 위치마다 해당 위치에서 끝나는 최대합을 기록하며 풀이해도 되는데 이번 문제에선 중간 내용을 활용하지 않기 때문에 그냥 변수에 바로 저장해서 풀이했습니다.

if-else구문을 max(i, sum+i)로 줄이면 코드라인은 줄어들지만 실행시간이 조금 느려집니다.

조건문을 (0 > sum)으로 작성해도 같은 코드입니다.

class Solution:
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[-2,1,-3,4,-1,2,1,-5,4],[1],[5,4,-1,7,8]]
for i in input:
    print(Solution().maxSubArray(i))