最大m子段和

如题= =自用模板

import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		//dp[i][j]=Math.max(dp[i][j-1]+shu[j], dp[i-1][t]+shu[j]);
		while(sc.hasNext()){
			int m=sc.nextInt();
			int n=sc.nextInt();
			int[]shu=new int[n+1];
			//premax:dp[i-1][t]的最大值
			//dp[j]每次为分了i段,以第j位作为最后一段的最后一个 这里用了滚动数组
			int[]premax=new int[n+1];
			int[]dp=new int[n+1];
			for(int i=1;i<=n;i++)shu[i]=sc.nextInt();
			dp[0]=0;
			int max=0;
			for(int i=1;i<=m;i++){
				max=-0x3f3f3f3f;
				for(int j=i;j<=n;j++){
					dp[j]=Math.max(dp[j-1]+shu[j],premax[j-1]+shu[j]);
					premax[j-1]=max;
					max=Math.max(max, dp[j]);
				}
			}
			pw.println(max);
			pw.flush();
		}
	}

}