牛客网2019真题-20善良的同伴（m段最大子序和）

折磨了好久，还是80%，这道题java动态规划过不了，算了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        //        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        //        int[] mn = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //        int N = mn[0];
        //        int M = mn[1];
        //        long[] ints = Arrays.stream(sc.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] ints = new int[N];
        int len = 0;
        ints[0] = sc.nextInt();
        for(int i = 1; i < N; i++){
            ints[i] = sc.nextInt();
            if(ints[i] * ints[len] >= 0){
                ints[len] += ints[i];
            }else{
                len++;
                ints[len] = ints[i];
            }
        }
        ints = Arrays.copyOfRange(ints, 0, len + 1);
        int m = 0;
        int sum = 0;
        for(int i = 0; i < ints.length; i++){
            if(ints[i] > 0){
                m++;
                sum += ints[i];
            }
        }
        if(m <= M){
            System.out.println(sum);
        }else{
            //            long[][] dp = new long[M + 1][ints.length + 1];
            ////            System.out.println(dp.length + " " + dp[0].length);
            //            for(int i = 1; i < dp.length; i++){
            //                long max = 0;
            //                for(int j = i; j < dp[0].length; j++){
            //                    //这里用max来表示dp[i-1][t]的最大值
            //                    max = Math.max(max, dp[i - 1][j - 1]);
            //                    dp[i][j] = Math.max(dp[i][j - 1], max) + ints[j - 1];
            //                }
            //            }
            //            long ans = 0;
            //            for(int i = 1; i < dp[0].length; i++){
            //                ans = Math.max(ans, dp[M][i]);
            //            }
            //            System.out.println(ans);
            //System.out.println(Arrays.toString(ints));
            long res = 0;
            int n = ints.length;
            long[] dp = new long[n + 1];
            long[] maxArray = new long[n + 1];
            for(int i = 1; i <= M; i++){
                res = Long.MIN_VALUE;
                for(int j = i; j < dp.length; j++){
                    dp[j] = Math.max(dp[j - 1], maxArray[j - 1]) + ints[j - 1];
                    if(res < dp[j]) res = dp[j];
                    maxArray[j - 1] = res;
                }
                //System.out.println("  " + Arrays.toString(dp));
            }

            System.out.println(res);
        }
    }
}