昨晚链家笔试第一题，食品那题，代码
开始用贪心就过了27%，后来考虑首尾数值相等的情况还是27%，所以想着换动态规划，然而当时递推式写错了，初始值错了，后面也有小错误，导致一直不对，今天早上写了下，样例是对的，找不到测试的地方不知道能不能AC。
原题：
动态规划：dp[i][j]表示0到i-1和n-1到j+1的食物都买出后，从第i个开始到第j个食物能获得的最大价值。
dp[i][j] = max{dp[i][j-1]+cnt*a[j] , dp[i+1][j]+cnt*a[i]) cnt = n - (j-i), j > i
dp[i][i] = n*a[i], 从上面的递推式其实就能推出初值的表达式，但是当时虽然写了动态规划但是对dp[i][j]
的实际含义不是很透彻，所以写错了。
代码：
import java.util.*;
public class Main{
public static void main(String[] arg){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; ++i){
a[i] = sc.nextInt();
}
int[][] dp = new int[n][n];
for(int i = 0; i < n; ++i){
dp[i][i] = n*a[i];
}
for(int l = 1; l <= n-1; ++l){
for(int i = 0; i + l < n; ++i){
int j = i + l;
int cnt = n - (j-i);
dp[i][j] = Math.max(dp[i+1][j] + cnt*a[i], dp[i][j-1]+cnt*a[j]);
}
}
System.out.println(dp[0][n-1]);
}
}
#算法工程师#
