解题思路

要求在保持原相对顺序的前提下，从长度为 $n$ 的数组中恰好选出 $k$ 个元素，使其和最大。设

转移分两类（划分型动态规划的典型“选/不选当前元素”）：

题面描述

给定一个长度为$n$的数组$[a_1,a_2,...,a_n]$，问从中选出$k$ 个元素的最大和是多少？

注:不允许改变数组本身的顺序。使用课上学习的划分型动态规划方法去实现！

输入输出

输入： 第一行包含两个整数 $n,k$。

第二行包含$n$个整数$a_1,a_2,a_3,...,a_n$

输出： 一行输出一个整数，即从 $a_1,a_2,a_3,...,a_n$ 中选出 $k$ 个元素能得到的最大和

数据范围

• $1 \le n \le 1000$
• $0 \le k \le n$
• $-1000 \le a_i \le 1000$

样例1

输入

3 2
3 1 2

输出

5

说明 选出$[3,2]$ 的和最大，为$3+2=5$

样例2

输入

5 3
-1 -2 -3 4 5

输出

8

说明 选出$[-1,4,5]$ 的和最大，为$-1+4+5=8$