分隔数组以得到最大和

/*
 * 思路：
 * 使用动态规划和Java Stream API来简化代码。
 * 我们仍然使用一个dp数组来存储前i个元素的最大和。
 * 对于每个位置i，我们向前最多看k个元素，计算可能的分隔，并选择最大的分隔。
 */
import java.util.stream.IntStream;

public class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        IntStream.rangeClosed(1, n).forEach(i -> {
            int[] max = {0};
            IntStream.rangeClosed(1, Math.min(k, i)).forEach(j -> {
                max[0] = Math.max(max[0], arr[i - j]);
                dp[i] = Math.max(dp[i], dp[i - j] + max[0] * j);
            });
        });
        return dp[n];
    }
}