가장 큰 값
면접 대비시간 제한2초메모리 제한512 MB
길이 20 이하의 배열에서 서로 겹치지 않는 연속 구간 M개를 골라 원소 합의 최댓값을 구한다.
문제
N개의 정수로 이루어진 수열이 주어진다. 주어진 수열에서 연속된 1개 이상의 수로 이루어진 부분 수열을 "그룹"이라고 하자. 양의 정수 M이 주어졌을 때 M개의 그룹을 선택해서 그룹에 속한 모든 수의 합의 최댓값을 구하는 프로그램을 작성하라.
입력
첫째 줄에 N과 M(1 ≤ M ≤ N ≤ 20)이 주어진다. 둘째 줄에는 수열에 속한 수가 주어진다. 수는 공백으로 구분되어져 있고, 절댓값이 100보다 작거나 같은 정수이다.
출력
첫째 줄에 M개의 그룹을 선택했을 때, 그룹에 속한 모든 수의 합의 최댓값을 출력한다.