欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组轮流取头或尾的最大值

程序员文章站 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);
	}