순이익이 가장 큰 연속 구간

자바스크립트 코딩테스트 문제로 kadane 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium kadane 함수명: maxNetGainWindow 제한 시간: 250ms

하루별 손익 변화가 담긴 배열에서 합이 가장 큰 연속 구간의 값을 구하는 문제입니다.

문제 설명

정수 배열 changes가 주어집니다.

changes[i]는 어떤 기간의 i번째 날에 생긴 순변화를 뜻합니다.

양수면 이익
음수면 손실
0이면 변화 없음

이때 비어 있지 않은 연속 구간 하나를 골라 얻을 수 있는 합의 최댓값을 반환하는 maxNetGainWindow 함수를 작성하세요.

즉, 배열에서 서로 붙어 있는 일부 원소를 하나 이상 골랐을 때 만들 수 있는 가장 큰 합을 구하면 됩니다.

제한사항

1 <= changes.length <= 100,000
-1,000,000 <= changes[i] <= 1,000,000
입력은 모두 정수입니다.
반드시 원소를 하나 이상 선택해야 합니다.
반환값은 가능한 연속 구간 합의 최댓값입니다.

예시

입력: changes = [4, -1, 2, 1, -5, 4] → 출력: 6
입력: changes = [-3, -1, -2] → 출력: -1
입력: changes = [5, -2, 3, -1, 2] → 출력: 7

첫 번째 예시에서는 [4, -1, 2, 1]을 고르면 합이 6이 되어 최댓값입니다.

힌트

어떤 위치에서 끝나는 최적 구간만 알면 다음 위치를 판단할 수 있습니다.
현재 값을 기존 구간 뒤에 붙이는 것이 유리한지, 현재 위치에서 새로 시작하는 것이 유리한지 비교해 보세요.
전체 구간을 모두 시도하면 너무 느립니다.

해설

이 문제의 핵심은 현재 위치에서 끝나는 최대 연속 구간 합을 관리하는 것입니다.

배열을 왼쪽부터 보면서, 각 값 x에 대해 두 선택지만 생각하면 됩니다.

바로 이전까지의 좋은 구간 뒤에 x를 이어 붙인다.
이전 구간은 버리고 x 하나로 새 구간을 시작한다.

그래서 현재 상태는 다음처럼 갱신됩니다.

current = max(x, current + x)
best = max(best, current)

예를 들어 changes = [4, -1, 2, 1, -5, 4]라면:

4 → 현재 최대 4, 전체 최대 4
-1 → 이어 붙이면 3, 새 시작은 -1 → 현재 3
2 → 이어 붙이면 5, 새 시작은 2 → 현재 5
1 → 이어 붙이면 6, 새 시작은 1 → 현재 6
이후 값을 봐도 전체 최대는 6

중요한 점은 모든 값이 음수인 경우입니다. 이때 빈 구간을 허용하면 0을 답으로 내기 쉽지만, 이 문제는 반드시 하나 이상 선택해야 하므로 [-3, -1, -2]의 정답은 -1이어야 합니다. 그래서 current를 무조건 0으로 리셋하지 말고, 항상 x와 current + x 중 큰 값을 고르는 방식으로 처리해야 합니다.

이 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간은 O(1)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과