Python程序：查找“有效”数组的最大值

假设我们有一个包含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，执行以下操作：

    • 如果table中不存在j，则

      • table[j] := 一个新的对(i, 0)

      • 否则，

        • table[j, -1] := i

      • 向prefix添加一个新元素，该元素等于prefix的最后一个元素 + j

      • 复制negative的最后一个元素

      • 如果j < 0，则

        • negative的最后一个元素 := negative的最后一个元素 + j

  • ans := 负无穷大

  • 对于table的所有值中的每个对(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]))

输入

[3, 4, 5, 3, 4]

输出

16

更新于： 2021年10月8日

185 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告