用 Python 编写程序找出"有效"数组的最大值

pythonserver side programmingprogramming更新于 2025/12/14 2:52:17

假设我们有一个包含 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[j] := 一个新的对 (i, 0)
  - 否则，
    - table[j, -1] := i
  - 向 prefix 添加一个等于 prefix + j 的最后一个元素的新元素
  - 复制 negative 的最后一个元素
  - if 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]))