순환 배송 트랙의 최대 이익 구간

문제

도심 순환 배송 트랙은 n개의 구간으로 나뉘어 있고, 마지막 구간을 지나면 다시 0번 구간으로 이어집니다. 배송 차량이 i번 구간을 통과하면 profits[i]만큼의 손익이 발생합니다 (수익이면 양수, 비용이면 음수).

운행 계획은 어느 구간에서든 출발해 연속된 구간들을 달린 뒤 멈추는 방식입니다.

• 최소 1개 구간은 달려야 합니다.
• 같은 구간을 두 번 지날 수 없으므로 최대 n개 구간까지만 달릴 수 있습니다.
• 트랙이 순환하므로 n-1번 구간에서 0번 구간으로 이어지는 운행도 가능합니다.

손익 배열 profits가 주어질 때, 얻을 수 있는 최대 이익과 그때 달린 구간 개수를 [이익, 구간 개수] 형태의 배열로 반환하는 solution(profits) 함수를 작성하세요. 최대 이익이 같은 운행이 여러 가지라면 구간 개수가 더 적은 쪽을 답으로 합니다.

예시

제약 조건

• 1 ≤ profits.length ≤ 100,000
• -30,000 ≤ profits[i] ≤ 30,000
• 반환값은 길이 2의 number[]이며, 두 번째 값은 항상 1 이상 n 이하입니다.

시간 복잡도 목표: O(n)

공간 복잡도 목표: O(1)