牛客刷题：获得最多的奖金（编程题）

题目描述： 小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。 现在主持人给要求小明在这一列红包之间“切”2刀，将这一列红包“切”成3组，并且第一组的奖金之和等于最后一组奖金和（允许任意一组的红包集合是空）。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少，你能帮他算算吗。

举例解释：桌子上放了红包 1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀，将红包分成3组 [1, 2, 3, 4] [7] [10]，其中第一组奖金之和=第三组奖金之和=10，所以小明可以拿到10越南盾。

解： n=int(input()) a=list(map(int,input().strip().split(" "))) i=0 j=n-1 sum1=a[0] sum2=a[n-1] res=[] while i<j: 　if sum1<sum2: 　　 i+=1 　　sum1+=a[i] 　elif sum1>sum2: 　　j-=1 　　sum2+=a[j] 　elif sum1==sum2: 　　res.append(sum1) 　　 i+=1 　　 j-=1 　　sum1 += a[i] 　　 sum2 += a[j] res=sorted(res) if len(res)==0: 　print(“0”) elif len(res)>0: 　print(res[-1])

总结： 1.采用二分查找法，也就是用两个指针，一个放在第一个元素，一个放在最后一个元素，然后利用循环，设定while i<j的限定条件，使得一边统计两个和，指针一边向中间集中。 2.把每次得出的相等的值都放在一个列表里，方便取最大值。 3.需要注意的是处理临界值，这里我采用统计列表中的个数，来实现判别。 4.这个题最大的难点，我认为是在，两个指针。如果两个和，哪一方小就让这一方的指针向对方靠近。 5.这个题其实还可以更复杂。比方说，这些数里面如果有负数怎么办，那么我推荐先对这些数字进行排序再进行二分查找操作。