Pythonのジャンプゲームで取得できる最大スコアを見つけるためのプログラム

numsという配列と別の値kがあるとします。インデックス0にいます。1回の移動で、配列の境界の外に出ることなく、最大でkステップ右にジャンプできます。配列の最終インデックスに到達したいと思います。ジャンプの場合、スコアを取得します。これは、配列内でアクセスした各インデックスjのすべてのnums[j]の合計です。取得できる最大スコアを見つける必要があります。

したがって、入力がnums =[1、-2、-5,7、-6,4] k =2のような場合、このシーケンスでジャンプするため、出力は10になります[1、-2、7、 4]、それから私達は最大のポイントを得るでしょう、そしてそれは10です。

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

• n：=numsのサイズ
• score：=サイズnで、0で埋められた配列
• score [0]：=nums [0]
• currMax：=スコア[0]
• max_pt：=0
• n <1の場合、
  • 0を返す
• nが1と同じ場合、
  • numsの最後の要素を返す
• 1〜n -1の範囲のidxの場合、do
  • max_pt> =idx --kの場合、
    • currMax0の場合、
      • currMax：=スコア[idx-1]
      • max_pt：=idx-1
  • それ以外の場合、
    • idx --k> 0の場合、
      • currMax：=スコア[idx-k]
      • max_pt：=idx --k
      • idx-kからidxの範囲のpについては、
        • スコア[p]>=currMaxの場合、
          • max_pt：=p
          • currMax：=スコア[p]
  • score [idx]：=currMax + nums [idx]
• スコアの最後の要素：=currMax + nums [-1]
• スコアの最後の要素を返す

例

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

def solve(nums, k):
   n = len(nums)
   scores = [0] * n
   scores[0] = nums[0]
   currMax = scores[0]
   max_pt = 0

   if n < 1:
      return 0
   if n == 1:
      return nums[-1]

   for idx in range(1,n):
      if max_pt >= idx - k:
         if currMax < scores[idx-1] and idx > 0:
            currMax = scores[idx-1]
            max_pt = idx-1
      else:
         if idx - k > 0:
            currMax = scores[idx-k]
            max_pt = idx - k
            for p in range(idx-k, idx):
               if scores[p] >= currMax:
                  max_pt = p
                  currMax = scores[p]
      scores[idx] = currMax + nums[idx]
   scores[-1] = currMax + nums[-1]
   return scores[-1]

nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))

入力

[1,-2,-5,7,-6,4], 2

出力

10