Pythonでターゲット配列を形成するための部分配列の最小増分回数を求めるプログラム

問題の概要

正の値からなる配列 target が与えられているとします。また、同じサイズで、すべての要素が0である配列 initial も用意します。このとき、次の操作を繰り返して initial を target に一致させるために必要な最小の操作回数を求めます。

操作の定義： initial から任意の部分配列（連続する区間）を選び、その範囲内の各要素の値を1ずつ増やします。

具体例

入力が target = [2,3,4,3,2] の場合、出力は 4 になります。手順は以下の通りです。

1. 最初、配列は [0,0,0,0,0] です。
2. インデックス0〜4を選んで1増やす → [1,1,1,1,1]
3. 再びインデックス0〜4を選んで1増やす → [2,2,2,2,2]
4. インデックス1〜3を選んで1増やす → [2,3,3,3,2]
5. 最後にインデックス2を選んで1増やす → [2,3,4,3,2]（ターゲットと一致）

合計4回の操作でターゲット配列が完成しました。

解法のアプローチ

この問題は、隣接する要素間の差に着目することで効率的に解けます。配列を左から右へ走査し、現在の値が前の値よりも大きい場合、その差の分だけ新たな操作を開始する必要があります。逆に、値が減少するか同じ場合は、すでに進行中の操作でカバーできるため、追加の操作は不要です。

• prev_num := 0（直前の要素の値。初期値は0）
• steps := 0(操作回数のカウンタ)
• target 内の各 val について以下を繰り返します。
  • val > prev_num の場合：steps += val - prev_num、それ以外は何もしない
  • prev_num := val として更新
• 最後に steps を返します。

実装例

以下のPythonコードで理解を深めましょう。

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

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加の記憶領域は O(1) で済みます。非常にシンプルかつ効率的な解法と言えるでしょう。