k-최대 부분 배열

여러분은 대학 학부 알고리즘 수업에서 "최대 부분 배열 문제"를 들어본 적이 있을 것이다. 문제는 이렇다. n개의 정수로 이루어진 배열 A가 주어질 때, 합이 최대가 되는 A의 연속 부분 배열을 찾는 것이 목표이다. 예를 들어 아래 배열에서:

A := [-2, 3, 5, -7, 8, 13, -20, 14, 1],

답은 두 번째 인덱스(3)부터 여섯 번째 인덱스(13)까지의 부분 배열이며, 총합은 22이다. 이 문제는 분할 정복으로 O(n log n) 시간에, 또는 동적 계획법으로 O(n) 시간에 풀 수 있다.

여러분은 알고리즘을 잘하는 학생이므로 두 방법 모두 익숙할 것이니 여기서 설명하지는 않겠다. 그런데 여러분의 동기인 Steve는 알고리즘을 그렇게 잘하지 못하는 학생인데도 최대 부분 배열 문제를 자랑하고 다녔다. 그는 자기가 최대 부분 배열 문제를 선형 시간에 풀 수 있을 뿐만 아니라, 자기가 "k-최대 부분 배열 문제"라고 부르는 것까지 선형 시간에 풀 수 있다고 주장한다! "k-최대 부분 배열 문제"가 무엇이냐고 묻자, Steve는 거만한 어조로 이렇게 설명한다. 그것은 최대 부분 배열 문제의 자연스러운 일반화이다. n개의 정수로 이루어진 배열 A가 주어질 때, 합이 최대가 되도록 A의 서로 겹치지 않는 k개의 연속 부분 배열을 찾아야 한다.

여러분은 Steve가 "k-최대 부분 배열 문제"를 선형 시간에 푸는 방법을 알고 있다는 것도, 심지어 선형 시간 해법이 존재한다는 것도 전혀 확신하지 못한다. 하지만 여러분은 알고리즘 수업을 한 번도 빠지지 않았고, 이는 Steve의 출석률에 비하면 거의 무한한 개선이므로, 이 문제의 권위자가 될 사람은 아마 자신일 것이라고 생각한다.

여러분은 "k-최대 부분 배열 문제"를 푸는 프로그램을 작성하기로 한다. 이것으로 Steve의 틀렸을 가능성이 높은 알고리즘을 검증할 수 있다. 단순화를 위해 프로그램은 최적해의 값만 출력하게 한다. 나중에 해 자체가 필요하면 수정할 수 있다. 또한 n과 k에 대한 작은 다항식으로 실행 시간이 제한되면 충분히 효율적인 알고리즘이라고 판단한다. 실제로 올바른 선형 시간 해법을 만드는 데는 시간이 꽤 걸릴 것이고, 여러분은 코드를 작성하는 데 최대 다섯 시간 정도만 쓰기로 했다.

입력은 두 줄로 이루어진다. 첫째 줄에는 정수 n과 k가 주어진다. (1 ≤ k ≤ n ≤ 5 000) 둘째 줄에는 배열 A를 나타내는 n개의 정수가 주어진다. 배열 A의 정수는 −109 이상 109 이하이다.

배열 A의 서로 겹치지 않는 k개의 연속 부분 배열의 총합으로 가능한 최댓값을 출력한다. 부분 배열들은 서로 겹치지 않아야 하지만, 한 부분 배열이 인덱스 i에서 끝나고 다른 부분 배열이 인덱스 i + 1에서 시작할 수는 있다. 부분 배열은 비어 있을 수 없다.