数组轮流取头或尾的最大值
程序员文章站
2022-07-14 14:37:58
...
方法一:递归
递推关系为:
M(left,right) = max(v[left] + L(left + 1,right) , v[right] + L(left, right - 1))
其中L(left,right) = Sum(left, right) - M(left, right)
其中M表示自己先选获得的最大值,L表示对方先选自己获得的最大值
package lianxi_1;
//有一个数组,a,b轮流取数字,每次只能从头或尾取,问先取的人最多取多少?
//暂时基于递归实现,动态规划递推式是有了,不过递推式中依赖更高index的项,不知咋办了。。
public class Exercise14 {
static int max(int[] a, int i, int j) {
int sum = 0;
while (i <= j) {
sum += a[i];
i++;
}
return act(a, sum, 0, a.length - 1);
}
private static int act(int[] a, int sum, int l, int r) {
int lmax, rmax;
if (r - l > 1) {
// 意思是先选一个,然后求剩下数组对方先选获得的最大值,用sum减去对方获得的最大值,即是自己的最大值
// 然后比较选头还是尾更好
lmax = sum - act(a, sum - a[l], l + 1, r);
rmax = sum - act(a, sum - a[r], l, r - 1);
return lmax > rmax ? lmax : rmax;
} else {//剩下2个
return a[l] > a[r] ? a[l] : a[r];
}
}
public static void main(String[] args) {
int v[] = { 1, 2, 3, 6, 9, 5, 7, 4, 2, 6, 9, 5, 8, 7, 2, 1, 55, 3, 6, 9, 7, 5, 2 };
int n = max(v, 0, v.length - 1);
System.out.println(n);
}
}
方法二:动态规划
递推关系为:
dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])
dp[i][j]表示i到j获得的最大值,sum[i][j]表示i到j的总和
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a=new int[n+1];
int[][] dp=new int[n+1][n+1];
int[] sum=new int[n+1];
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
sum[i]=sum[i-1]+a[i];
dp[i][i]=a[i];
}
for(int i=n;i>0;i--){
for(int j=i+1;j<=n;j++){
dp[i][j]=sum[j]-sum[i-1]-Math.min(dp[i+1][j],dp[i][j-1]);
}
}
int first=dp[1][n];
int second=sum[n]-first;
System.out.println(first+" "+second);
}
推荐阅读