문제

링크텍스트

해외에서 리트코드를 많이 푼다길래 한번 들어가서 Easy단계의 문제를 풀어보았다. 최대부분합 문제로 자료구조시간에 배웠던 문제였다.

코드

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

        return mxSum

리트 코드는 제출 방식이 class를 선언 후 그 메소드를 구현하는 방식이다. 배열이 [-2,1,-3,4,-1,2,1,-5,4] 으로 주어진다면 코드는 다음과 같은 방식으로 동작한다.

• 누적합인 sum과 i번째의 값의 합이 음수가 아니라면 계속 더해간다.
• sum+i가 0보다 작거나 같다면 sum을 0으로 초기화 시킨다.
• 반복이 끝날 때 마다 mxSum에 mxSum의 현재 값과 sum의 값 중 큰 값을 저장한다.

이렇게 구현하면 연속된 부분집합 중 가장 큰 값을 O(n)의 시간에 구현할 수 있다. 하지만 주어진 배열이 음수로만 이루어진 배열이라면 ex)[-2,-1,-3] 음수 값 중 가장 큰 값을 반환해주는 것으로 해결하였다.