人物1をチェックするプログラムは、Pythonで最大スコアを取得するかどうかによってキャンディーゲームに勝つことができます

したがって、入力がnums =[1、1、2、3、50]の場合、出力はTrueになります。これは、人1がキャンディーを1つ取ることができ、他のプレーヤーがキャンディーを1つ、2つ、または3つ取る必要があるためです。いずれにせよ、人1は50の値のキャンディーを取ることができます。

これを解決するには、次の手順に従います-

• n：=numsのサイズ

• table：=3つの0を持つ配列。

• n − 1から0の範囲のiの場合、1ずつ減らします。

  • 利益：=−inf

  • sum_val：=0

  • iからi+3およびnの最小値までの範囲のjについては、次のようにします

    • sum_val：=sum_val + nums [j]

    • 利益：=利益の最大値と（sum_val − table [j − i]）

  • set table：=3つの値を持つリスト[profit、table [0]、table [1]]

• table [0]> 0の場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう-

例

import math
class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [0, 0, 0]
      for i in range(n − 1, −1, −1):
         profit = −math.inf
         sum_val = 0
         for j in range(i, min(i + 3, n)):
            sum_val += nums[j]
            profit = max(profit, sum_val − table[j − i])
         table[:] = [profit, table[0], table[1]]
      return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))

入力

[1, 1, 2, 3, 50]

出力

True