HDU 1024ダイナミック企画問題

テーマ接続:http://acm.hdu.edu.cn/showproblem.php?pid=1024
Mセグメントが交わらないフィールドの和の最大値を求めるという意味です.
経典の動態計画
fk'[j]でKセグメントが選択された最大値を表します.
状態遷移方程式は、f[k][j]である.  = max｛f[k][j-1]＋a[j],max(f[k-1][t]＋a[j])｝

import java.util.Scanner;
public class HDU1024 {
	/*
	 *        
	 * f[k][j] //     1……j   ，    k      
	 * f[k][j] = max{f[k][j-1] + a[j], max{ f[k-1][t] + a[j]} t ∈ 1……j-1}}
	 * (1)  a[j]        k      f[k][j] = f[k][j-1]+ a[j]  
	 * (2)   j         K          k-1       + a[j]     max{ f[k-1][t] k-1<t<j-1 } 
	 *    f[k][]    f[k-1][]                 
	 */
	private int n,m;
	static private int inf = (-1)*1<<30;
	private int a[] ;
	private int f[];// 
	private int pre[];
	int max;
	public void solve(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			m = sc.nextInt();
			n = sc.nextInt();
			a = new int[n+1]; f = new int[n+1];pre = new int[n+1];
			for(int i=1;i<=n;i++){
				a[i] = sc.nextInt();
			}
			//   
			f[0] = 0; pre[0] = inf;
			for(int i=1;i<=m;i++){
				max = inf;
				for( int j=i;j<=n;j++){
					f[j] = f[j-1]>pre[j-1]?f[j-1]+a[j]:pre[j-1]+a[j];
					pre[j-1] = max;
					if( f[j] > max){
						max = f[j];
					}
				}
			}
			System.out.println(max);
		}
	}
	public static void main(String[] args) {
		new HDU1024().solve();
	}
}