Pythonでターゲット配列を形成するためのサブ配列の最小増分数を見つけるプログラム

正の値を持つtargetという配列があるとします。ここで、すべてゼロの同じサイズの配列イニシャルについて考えてみます。この操作を行う場合、イニシャルからターゲット配列を生成するために必要な最小数の操作を見つける必要があります:(イニシャルから任意のサブ配列を選択し、各値を1ずつインクリメントします。）

したがって、入力がtarget =[2,3,4,3,2]のようである場合、最初は配列が[0,0,0,0,0]であったため、出力は4になります。 4そしてそれを1増やすので、配列は[1,1,1,1,1]になり、次にインデックス0から4までを選択して[2,2,2,2,2]にし、から要素を選択します。インデックス1から3に増やすと、配列は[2,3,3,3,2]になり、最後にインデックス2を選択して、ターゲットと同じ配列[2,3,4,3,2]を作成します。

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

• prev_num：=0

• ステップ：=0

• ターゲットの各値について、実行します

  • ステップ：=ステップ+val-valの場合はprev_num>prev_numそれ以外の場合は0

  • prev_num：=val

• 戻る手順

例

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

def solve(target):
   prev_num = 0
   steps = 0
   for val in target:
      steps += val-prev_num if val > prev_num else 0
      prev_num = val
   return steps

target = [2,3,4,3,2]
print(solve(target))

入力

[2,3,4,3,2]

出力

4