18-算法训练 最大的算式

import java.util.Scanner;

public class Main1 {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n, k;
		n = cin.nextInt();
		k = cin.nextInt();
		long[][] dp = new long[n+1][n+1];
		long[] sum = new long[n+1];
		long t;
		//初始化dp数组
		for(int i = 0; i <= n; i++) {
			for(int j = 0; j <= k; j++) {
				dp[i][j] = 0;
			}
		}
		//得到累加和
		sum[0] = 0;
		for(int i = 1; i <= n; i++) {
			t = cin.nextLong();
			sum[i] = sum[i-1] + t;
			dp[i][0] = sum[i];
		}
		//计算:
		for(int i = 2; i <= n; i++) {     //数的个数
			for(int j = 1; j <= k; j++) { //乘号的个数
				for(int tt = 1; tt < i; tt++) { //遍历最后一个乘号的位置
					dp[i][j] = Math.max(dp[i][j], dp[tt][j-1] * (sum[i] - sum[tt])); 
				}
			}
		}
		System.out.println(dp[n][k]);
		cin.close();
	}
}