企业免费网站优化方案_长春网站建设大概需要多少钱_p2p万能搜索引擎_优化软件

假设有个游戏，一列牌有不同分数，但是只能从两头拿 ，拿到最后分数最高的人获胜，假设两个人都是聪明人，求最后的最高分是多少？

思路：递归算法，一个人拿左边牌，另一个人的得分 和拿右边牌 另一个人的得分作比较，只拿让对方得分最小的牌，反过来也是一样，那如果轮到对方拿牌自己也将会拿到最小的分，

两个方法，分别代表A 的最大得分 B的最大得分

private  static int getAMaxPoker(int []arr, int first, int end, boolean aFirst,int total){if(first==end){if(aFirst) {return arr[first];}else{return 0;}}if(aFirst) {int left = arr[first];int otherleft = getAMaxPoker(arr, first + 1, end, false,total-left);int right = arr[end];int otherright = getAMaxPoker(arr, first, end - 1,false,total-right);int lefttotal=left+otherleft;int righttotal=right+otherright;if(lefttotal>righttotal){return lefttotal;}else{return righttotal;}}else{return total- getBMaxPoker(arr,first,end,true,total);}}

private  static int getBMaxPoker(int []arr, int first, int end, boolean bFirst,int total) {if (first == end) {if (bFirst) {return arr[first];} else {return 0;}}if (bFirst) {int left = arr[first];int otherleft = getBMaxPoker(arr, first + 1, end, false,total-left);int right = arr[end];int otherright = getBMaxPoker(arr, first, end - 1, false,total-right);if (left + otherleft > right + otherright) {return left + otherleft;} else {return right + otherright;}}else{return total-getAMaxPoker(arr,first,end,true,total);}}

测试方法：

public static void main(String[] args) {int []arr={1,100,2};int sum=0;for (int i = 0; i < arr.length; i++) {sum+=arr[i];}int maxPoker = getAMaxPoker(arr, 0, arr.length - 1, true,sum);System.out.println((sum-maxPoker)>maxPoker?(sum-maxPoker):maxPoker);}