Python 中数组 K 次取反后最大和

假设我们有一个整数数组 A，我们需要按照以下方式修改数组：

我们可以选择一个索引 i 并将 A[i] 替换为 -A[i]，并且我们将重复此过程 K 次。我们需要返回通过这种方式更改数组后数组的最大可能总和。

因此，如果数组 A = [4,2,3]，并且 K = 1，则输出将为 5。因此，选择索引 1，数组将变为 [4,-2,3]

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

  • 对数组 A 进行排序

  • 对于 i 从 0 到 A 的长度 - 1

    • 如果 A[i] < 0，则 A[i] := - A[i]，并将 k 减 1

    • 如果 k = 0，则退出循环

  • 如果 k 为偶数，则

    • sp := A[0]

    • 对于 i 从 1 到 A 的长度 - 1

      • 如果 A[i] > 0，则 sp := sp 和 A[i] 的最小值

    • 返回 A 的元素之和 - (2*sp)

  • 否则，返回 A 的元素之和

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

class Solution(object):
   def largestSumAfterKNegations(self, A, K):
      A.sort()
      for i in range(len(A)):
         if A[i] <0:
            A[i] = -A[i]
            K-=1
         if K==0:
            break
      if K%2:
         smallest_positive = A[0]
         for i in range(1,len(A)):
            if A[i]>=0:
               smallest_positive = min(smallest_positive,A[i]) return sum(A) - (2*smallest_positive)
            else:
               return sum(A)
ob1 = Solution()
print(ob1.largestSumAfterKNegations([3,-1,0,2],3))

输入

[3,-1,0,2]
3

输出

6

更新于: 2020年4月27日

280 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告