数组分组

输入：

7
52 26 1 36 72 48 43

输出：

1596

pre[i][j]预处理从i到j分为一组的权值，dp[i]考虑前i-1位已经分好了，那么不断尝试前 j 位（dp[j]已经是最大值）和 j+1到 i 位 的最大值，并赋值给dp[i].

代码如下;

package Texun_12;

import java.util.Scanner;

public class L12 {

	static int maxn = 1010;
	static int mod = 1000;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 考虑最后一组分的哪一组
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n + 5];
		int[] dp = new int[n + 5];
		int[][] pre = new int[n + 5][n + 5];
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
		}
		for (int i = 1; i <= n; i++) {
			pre[i][i] = a[i];
			for (int j = i + 1; j <= n; j++) {// pre[i][j] -> 从i开始到j 一组的权值
				pre[i][j] = pre[i][j - 1] * a[j] % mod;// 每一段分组会造成的权值和
			}
		}
		dp[0] = 0;
		dp[1] = a[1];
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				dp[i] = Math.max(dp[i], dp[j] + pre[j + 1][i]);//dp[i], 前j位的和加上 j+1到i分为一组的和
			}
		}
		System.out.println(dp[n]);

	}

}