在 Python 中 K 次求反后最大化数组总和

pythonserver side programmingprogramming更新于 2025/10/25 8:44:17

假设我们有一个整数数组 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))