确定第一个玩家是否能赢得一场比赛

考虑下一个游戏。有一组正数。每个玩家依次移除一个切片(连续的元素序列),使其和为偶数。输球的球员是不能移动的球员。 对于 [4, 5, 3, 7, 2] 例如,获胜策略(对于第一个玩家)是删除 [5,3] 切片。 您需要确定第一个玩家是否有获胜的动作(如果是,返回 slice_start 和 slice_end 索引)。

时间/空间复杂性: O(n)

我想到的一件自然的事情是计算从左到右的累积和,反之亦然。在 [4,5,3,7,2] 我们得到的例子是: acc_l = [4,9,12,19,21] 和 acc_r = [21,17,12,9,2] .

所以我几乎可以肯定这两个辅助阵列会派上用场,但我不能完全弄清楚。

我很乐意帮忙!