在Python中找到“valid”数组的最大值的程序

假设我们有一个包含n个整数“nums”的数组。 ‘nums’中的每个值都表示其“功率”。如果数组的长度大于2并且数组的第一个值和最后一个值相等，数组将被评估为“有效”。我们必须通过从数组中删除元素来使数组有效，以便其余部分满足条件。作为输出，我们通过添加数组的所有功率值来返回数组的最大可能功率值。

所以，如果输入是nums = [3, 4, 5, 3, 4]，那么输出将是16。

如果我们从数组nums中删除第一个值3，那么它就变成了[4, 5, 3, 4]。这是一个有效的数组，功率的总和为4 + 5 + 3 + 4 = 16。这是给定输入中任何有效数组的最大可能总和。

为了解决这个问题，我们将按照以下步骤进行-

table := 一个新地图
prefix := 初始化为值0的新列表
negative := 初始化为值0的新列表
对于nums中的每个索引i和值j，执行以下操作：
- 如果j不存在于table中，则
  - 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 := negative [j] – negative [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]))