小苯的序列分割1.0

import sys

T=int(input())
for t in range(T):
    n,m=list(map(int,input().strip().split()))
    a=list(map(int,input().strip().split()))
    if n==1 and m==1:
        print(a[0])
    else:
       
        dp=[[-float("inf")]*(1+m) for _ in range(1+n)]
        dp[0][0]=0
        presum=[0]*(n+1)
        for i in range(n):
            presum[i+1]=presum[i]+a[i]

        
        for i in range(1,n+1):
            
            for j in range(1,m+1):
                weight=1 if j%2 else 2
                best=-float("inf")
                for k in range(i):
                    best=max(best,dp[k][j-1]+(presum[i]-presum[k])*weight)
                dp[i][j]=best
        print(dp[n][m])




超时了

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]);
        }
    }
}