MarsCode-最大相等分割红包金额

最大相等分割红包金额

问题描述

小U在公司年会上运气极佳，赢得了一等奖。作为一等奖得主，他有机会在一排红包中做两次切割，将红包分成三部分，要求第一部分和第三部分的红包总金额相等。他可以获得的金额是第一部分红包的总金额。帮小U计算出他能从这些红包中拿到的最大奖金金额。

---

测试样例

样例1：

输入：redpacks = [1, 3, 4, 6, 7, 14]
输出：14

样例2：

输入：redpacks = [10000]
输出：0

样例3：

输入：redpacks = [10, 10, 10, 10]
输出：20

样例4：

输入：redpacks = [5, 5, 10, 20, 10, 5, 5]
输出：20

样例5：

输入：redpacks = [7, 7, 7, 21, 7, 7]
输出：14

解答

双指针解法

def solution(redpacks):
    # Please write your code here
    # 双指针
    i, j = 0, len(redpacks)-1
    first, third = 0, 0
    res = []
    while i <= j :
        if first < third:
            first += redpacks[i]
            i += 1
        elif third < first:
            third += redpacks[j]
            j -= 1
        else:
            res.append((i, j, first))
            if i != j:
                first += redpacks[i]
                i += 1
                third += redpacks[j]
                j -= 1
            else:
                break
    if first == third and i > j:
        res.append((i, j, first))
    i, j, ans = res[-1]
    return ans

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution([10, 10, 10, 10]) == 20)
    print(solution([1, 3, 4, 6, 7, 14]) == 14)
    print(solution([10000]) == 0)
    print(solution([52, 13, 61, 64, 42, 26, 4, 27, 25]) == 52)
    print(solution([2, 5, 50, 30, 60, 52, 26, 5, 74, 83, 34, 96, 6, 88, 94, 80, 64, 22, 97, 47, 46, 25, 24, 43, 76, 24, 2, 42, 51, 96, 97, 87, 47, 93, 11, 98, 41, 54, 18, 16, 11, 96, 34, 36, 87, 24, 32, 27, 62, 72, 54, 14, 67, 5, 21, 20, 44, 55, 3, 82, 19, 45, 1, 52, 14, 44, 46, 39, 83, 27, 30, 87, 61, 56, 59, 10, 83, 80, 42, 44, 75, 39, 43, 41, 23, 93, 73, 50, 94, 94, 82, 46, 87, 60, 94, 47, 52, 67, 22, 50, 49, 8, 9, 30, 62, 87, 13, 11]) == 2627)