Pythonでnums[i] + nums[j] + (i - j)を最大化するペア(i, j)を見つけるプログラム

問題の概要

数値のリスト nums が与えられたとき、i < j を満たすペア (i, j) の中から、nums[i] + nums[j] + (i - j) の値が最大になるものを見つけることを考えます。

例として、入力が nums = [6, 6, 2, 2, 2, 8] の場合、出力は 11 になります。インデックス 0 と 1 の2つの「6」を選ぶと、スコアは 6 + 6 + (0 - 1) = 11 となり、これが最大値となるためです。

解法のアプローチ

この式は次のように変形できます。

nums[i] + nums[j] + (i - j) = (nums[i] + i) + (nums[j] - j)

つまり、各 j について「それより前の位置における nums[i] + i の最大値」が分かれば、全体の最大値を一度の走査で求められます。変数 large にこれまで見てきた nums[i] + i の最大値を保持し、ループのたびに 1 を引いて位置の差分(距離のペナルティ)を調整しながら更新していきます。

アルゴリズムの手順

• large := nums[0]、maxi := 0 で初期化する

• i を 1 から nums のサイズまで順に処理する

  • large から 1 を引く

  • maxi を max(large + nums[i], maxi) で更新する

  • large を max(large, nums[i]) で更新する

• 最後に maxi を返す

実装例(Python)

class Solution:
    def solve(self, nums):
        large = nums[0]

        maxi = 0
        for i in range(1, len(nums)):
            large -= 1
            maxi = max(large + nums[i], maxi)
            large = max(large, nums[i])

        return maxi

ob = Solution()
nums = [6, 6, 2, 2, 2, 8]
print(ob.solve(nums))

入力

[6, 6, 2, 2, 2, 8]

出力

11

計算量

配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。すべてのペアを総当たりする O(n²) の方法と比べて大幅に効率的であり、大規模なデータにも対応できます。