Pythonで「有効な」配列の最大値を見つけるプログラム

n個の整数'nums'の配列があるとします。 'nums'の各値は、その'power'を表します。配列の長さが2より大きく、配列の最初と最後の値が等しい場合、配列は「有効」と評価されます。残りの要素が条件を満たすことができるように、配列から要素を削除して配列を有効にする必要があります。出力として、アレイのすべての電力値を加算することにより、アレイの可能な最大電力値を返します。

したがって、入力がnums =[3、4、5、3、4]の場合、出力は16になります。

配列numsから最初の値3を削除すると、[4、5、3、4]になります。これは有効な配列であり、累乗の合計は4 + 5 + 3 + 4 =16です。これは、指定された入力からの有効な配列の可能な最大合計です。

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

• テーブル：=新しいマップ

• prefix：=値0で初期化された新しいリスト

• 負：=値0で初期化された新しいリスト

• インデックスiと値j（nums）ごとに、実行します

  • jがテーブルに存在しない場合、

    • table [j]：=新しいペア（i、0）

    • それ以外の場合

      • table [j、-1]：=i

    • プレフィックス+jの最後の要素に等しい新しい要素をプレフィックスに追加します

    • ネガティブの最後の要素を複製する

    • j <0の場合、

      • 負の最後の要素：=負の最後の要素+ j

• ans：=負の無限大

• テーブルのすべての値の各ペア（i、j）について、実行します

  • jが0と同じでない場合、

    • sm1：=prefix [j +1]-prefix [i]

    • j> i + 1の場合、

      • sm2：=ネガティブ[j]-ネガティブ[i + 1]

    • それ以外の場合

      • sm2：=0

    • ans：=最大（ans、sm1-sm2）

• ansを返す

例

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

def solve(nums):
   table = {}
   prefix = [0]
   negative = [0]
   for i, j in enumerate(nums):
      if j not in table:
         table[j] = [i, 0]
      else:
         table[j][-1] = i
      prefix += prefix[-1] + j,
      negative += negative[-1],
      if j < 0:
         negative[-1] += j

   ans = float('-inf')
   for i,j in table.values():
      if j != 0:
         sm1 = prefix[j+1] - prefix[i]
         sm2 = negative[j] - negative[i+1] if j > i+1 else 0
         ans = max(ans, sm1 - sm2)
   return ans

print(solve([3, 4, 5, 3, 4]))

入力

[3, 4, 5, 3, 4]

出力

16