练习一下DP
C# code:
public class Solution {
public int MaxSumAfterPartitioning(int[] arr, int k) {
int n = arr.Length;
int[] dp = new int[n+1];
int max;
for (int i=1; i<=n; i++)
{
max = 0;
for (int j=1; j<=Math.Min(i,k); j++)
{
max = Math.Max(max, arr[i-j]);
dp[i] = Math.Max(dp[i], dp[i-j] + max*j);
}
}
return dp[n];
}
}