Python 程序查找最大擦除值

假设我们有一个名为 nums 的数组（仅包含正值），我们想要擦除一个包含唯一元素的子数组。我们将获得一个分数，即子数组元素的总和。我们必须找到通过精确擦除一个子数组可以获得的最大分数。

因此，如果输入类似于 nums = [6,3,2,3,6,3,2,3,6]，则输出将为 11，因为这里的最佳子数组是 [6,3,2] 或 [2,3,6]，所以总和为 11。

为了解决这个问题，我们将遵循以下步骤 -

  • seen := 一个新的映射
  • ans := sum := 0
  • l := 0
  • 对于每个索引 r 和值 x nums，执行
    • 如果 x 出现在 seen 中，则
      • index := seen[x]
      • 当 l <= index 时，执行
        • 删除 seen[nums[l]]
        • sum := sum - nums[l]
        • l := l + 1
    • seen[x] := r
    • sum := sum + x
    • ans := ans 和 sum 的最大值
  • 返回 ans

示例

让我们看看以下实现以获得更好的理解 -

def solve(nums):
   seen = dict()
   ans = sum = 0
   l = 0
   for r, x in enumerate(nums):
      if x in seen:
         index = seen[x]
         while l <= index:
            del seen[nums[l]]
            sum -= nums[l]
            l += 1

      seen[x] = r
      sum += x
      ans = max(ans, sum)
   return ans

nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))

输入

[6,3,2,3,6,3,2,3,6]

输出

11

更新于: 2021年10月6日

115 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告