小苯的序列分割1.0

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextLong();
            }

            // 前缀和
            long[] prefix = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                prefix[i] = prefix[i - 1] + a[i];
            }

            // dp[i][j] 表示前 i 个数划分为 j 段的最大值
            long[][] dp = new long[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
                Arrays.fill(dp[i], Long.MIN_VALUE / 2);
            }
            dp[0][0] = 0;

            // 动态规划
            for (int j = 1; j <= m; j++) {
                int weight = (j % 2 == 1 ? 1 : 2);

                // best[k] = max(dp[k][j-1] - prefix[k]*weight)
                long best = Long.MIN_VALUE / 2;

                for (int i = 1; i <= n; i++) {
                    // 先更新 best (相当于枚举k=i-1)
                    best = Math.max(best, dp[i - 1][j - 1] - prefix[i - 1] * weight);

                    // 再利用 best 转移到 dp[i][j]
                    dp[i][j] = prefix[i] * weight + best;
                }
            }

            System.out.println(dp[n][m]);
        }
    }
}