파이썬(Python)으로 최대 오름차순 부분 배열 합계 구하기

문제 개요

양수로만 이루어진 배열 nums가 주어졌을 때, 이 배열에서 만들 수 있는 오름차순(증가) 부분 배열의 최대 합을 구하는 문제입니다.

부분 배열 [nums_l, nums_l+1, ..., nums_r]이 오름차순이라는 것은 l <= i < r을 만족하는 모든 인덱스 i에 대해 nums[i] < nums[i+1]이 성립한다는 의미입니다.

예를 들어 입력이 nums = [15, 25, 35, 5, 15, 55]라면 결과는 75가 됩니다. 이는 [5, 15, 55]가 합이 가장 큰 증가 부분 배열이기 때문입니다.

접근 방법

이 문제는 카데인 알고리즘(Kadane's Algorithm)과 유사한 방식으로, 배열을 한 번만 순회하여 해결할 수 있습니다. 배열을 왼쪽에서 오른쪽으로 훑으면서 현재 연속된 증가 구간의 합을 계속 추적하면 됩니다.

1. total과 max_total을 첫 번째 요소 값으로 초기화합니다.
2. 두 번째 요소부터 마지막 요소까지 순회하며 다음을 수행합니다.
   • 현재 값이 이전 값보다 크면(증가 구간이 이어지면) total에 현재 값을 더합니다.
   • 그렇지 않으면 새로운 증가 구간이 시작되는 것이므로 total을 현재 값으로 초기화합니다.
3. 매 단계마다 total이 max_total보다 크면 max_total을 갱신합니다.
4. 순회가 끝나면 max_total을 반환합니다.

구현 예제

def solve(nums):
    total = nums[0]
    max_total = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            total += nums[i]
        else:
            total = nums[i]
        if total > max_total:
            max_total = total
    return max_total

nums = [15, 25, 35, 5, 15, 55]
print(solve(nums))

입력

[15, 25, 35, 5, 15, 55]

출력

75

복잡도 분석

배열 전체를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 변수는 두 개뿐이므로 공간 복잡도는 O(1)입니다. 따라서 매우 큰 배열에서도 효율적으로 동작합니다.