N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11
-4 13一段，6一段，和为26。
-4 13一段，6一段，和为26。
Input
第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000) 第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和
Input 示例
7 2 -2 11 -4 13 -5 6 -2
Output 示例
26
分析：
注意题目要求必须分为M个子段，并且并非数组中的所有元素都必须划到某以段中去。
最大子段和第一反应必须是dp啊！！
我们建立这样一个DP方程：
dp( i, j ) 表示前 i 个元素划分成 j 个字段能取得的最大和，并且第 i 个元素必须在（也只能在）第 j 个子段中。
所以有这样两种情况： 第i 个元素自己单独成为第j 段，然后前面的元素再分段，但注意并非简单的转移到 dp( i-1,j-1 )，因为很可能第 i-1 个元素最后根本不包含在任何一个子段当中，所以要枚举 k , 此时 dp ( i , j ) = max ( dp( k, j-1 ) + a[i] ) | j-1<=k < i ，
另一种情况是第i个元素划到最后一段当中，很明显 dp ( i , j ) = dp ( i-1, j ) + a[i] ；
所以动态转移方程如分析所示，两个情况取最大就是 dp (i , j )。
代码稍后再写。