Pythonで最大消去値を見つけるプログラム

nums（正の値のみ）という配列があり、一意の要素を含むサブ配列を消去するとします。サブアレイ要素の合計であるスコアを取得します。正確に1つのサブアレイを消去することで得られる最大スコアを見つける必要があります。

したがって、入力がnums =[6,3,2,3,6,3,2,3,6]のような場合、最適なサブ配列は[6,3,2]または[2,3,6]なので、合計は11です。

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

• 見た：=新しい地図
• ans：=sum：=0
• l：=0
• インデックスrと値xnumごとに、実行します
  • xが表示されている場合、
    • インデックス：=見た[x]
    • l <=インデックス、do
      • 見たものを削除する[nums[l]]
      • sum：=sum-nums [l]
      • l：=l + 1
  • sawed [x]：=r
  • 合計：=合計+ x
  • ans：=ansと合計の最大値
• 回答を返す

例

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

def solve(nums):
   seen = dict()
   ans = sum = 0
   l = 0
   for r, x in enumerate(nums):
      if x in seen:
         index = seen[x]
         while l <= index:
            del seen[nums[l]]
            sum -= nums[l]
            l += 1

      seen[x] = r
      sum += x
      ans = max(ans, sum)
   return ans

nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))

入力

[6,3,2,3,6,3,2,3,6]

出力

11