Pythonで配列式 values[i] + values[j] + nums[j] − nums[i] を最大化する値を求めるプログラム

問題の概要

整数を要素とする2つの配列 nums と values が与えられます。nums の要素は厳密に増加(狭義単調増加)しており、2つの配列の長さは同じです。

このとき、i ≤ j を満たすインデックスの組 (i, j) に対して、次の式で定義される値 v を考えます。

v = values[i] + values[j] + nums[j] − nums[i]

この v を最大化する値を求めるのが本記事のゴールです。

入力例

nums = [1, 2, 7]
values = [-4, 6, 5]

i = 1、j = 2 を選ぶと、計算は次のようになります。

6 + 5 + 7 − 2 = 16

よって出力は 16 となります。

解き方のポイント:式の分解

まず、対象の式を2つの項に分解してみましょう。

v = (values[j] + nums[j]) + (values[i] − nums[i])

前半は「インデックス j だけの関数」、後半は「インデックス i だけの関数」になっています。つまり、2つの項をそれぞれ独立に最大化できればよいことが分かります。

ただし、本来は「i ≤ j」という制約があるため、本当に独立に最大化してよいのかが気になるところです。ここで効いてくるのが、nums が厳密に増加しているという条件です。

もし i > j となる組を選んだ場合、同じ2つのインデックスを入れ替えた組 (j, i) を考えると、その値は

values[j] + values[i] + nums[i] − nums[j]

となり、nums[i] > nums[j] なので元の値よりも必ず大きくなります。言い換えれば、最適な組は必ず i ≤ j を満たすため、順序の制約を意識せずに各項を独立に最大化し、足し合わせるだけで正しい答えが得られます。

アルゴリズムの手順

• ans1 := −∞、ans2 := −∞ で初期化する

• i を 0 から nums のサイズ − 1 まで動かしながら、以下を繰り返す

  • ans1 := ans1 と (values[i] − nums[i]) のうち大きい方

  • ans2 := ans2 と (values[i] + nums[i]) のうち大きい方

• ans1 + ans2 を返す

この方法なら、配列を一度走査するだけで答えが求まります。

Pythonでの実装例

from math import inf

def solve(nums, values):
    ans1 = -inf
    ans2 = -inf
    for i in range(len(nums)):
        ans1 = max(ans1, values[i] - nums[i])
        ans2 = max(ans2, values[i] + nums[i])
    return ans1 + ans2

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

入力

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

出力

16

計算量

• 時間計算量: O(n) — 配列を1回走査するだけです。
• 空間計算量: O(1) — 変数2つだけで済みます。

まとめ

式を「j に依存する項」と「i に依存する項」に分解できるかどうかが最大のポイントです。nums が厳密に増加しているおかげで i ≤ j の制約が実質的に不要になり、1回のループで O(n) という非常に効率的な解法が実現できます。「式の分解 + 各項の独立最大化」というテクニックは、配列を使った最適化問題で頻出のパターンなので、ぜひ覚えておきましょう。