Pythonでの操作後の最大サブ配列の合計を見つけるプログラム

整数を含む配列が与えられたとします。 array[i]の値をその2乗値に置き換えることができる操作を実行できます。またはarray[i]*array[i]。この種の操作は1つだけ許可されており、操作後に可能な最大のサブ配列の合計を返す必要があります。サブアレイを空にすることはできません。

したがって、入力がarray =[4、1、-2、-1]のような場合、出力は17になります。

array [0]の値をその二乗値に置き換えると、配列は[16、1、-2、-1]になります。これから可能な最大サブアレイは[16、1]であり、最大合計値は16 + 1=17です。

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

• dp1：=負の無限大の値を含む新しいリスト
• dp2：=負の無限大の値を含む新しいリスト
• 配列内のnumごとに、
  を実行します。
  • dp1の最後に（（dp1の最後の要素+ num）、num）の最大値を挿入します
  • dp2の最後に最大（（dp1 + num ^ 2の最後から2番目の要素）、num ^ 2、（dp2 + numの最後の要素））を挿入します
• dp2の最大要素を返します

例

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

def solve(array):
   dp1 = [float('-inf')]
   dp2 = [float('-inf')]
   for num in array:
      dp1.append(max(dp1[-1] + num, num))
      dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
   return max(dp2)

print(solve([4, 1, -2, -1]))

入力

[4, 1, -2, -1]

出力

17