Tối đa hóa tổng của mảng sau khi K phủ định bằng Python

Giả sử chúng ta có một mảng A gồm các số nguyên, chúng ta phải sửa đổi mảng theo cách sau -

Chúng ta có thể chọn i và thay thế A [i] bằng -A [i], và chúng ta sẽ lặp lại quá trình này K lần. Chúng ta phải trả về tổng lớn nhất có thể của mảng sau khi thay đổi nó theo cách này.

Vì vậy, nếu mảng A =[4,2,3] và K =1, thì đầu ra sẽ là 5. Vì vậy, chọn chỉ số 1, mảng sẽ trở thành [4, -2,3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Sắp xếp mảng A

• cho tôi trong phạm vi từ 0 đến độ dài của A - 1

  • nếu A [i] <0, thì A [i]:=- A [i] và giảm k đi 1

  • nếu k =0, thì ngắt khỏi vòng lặp

• nếu k là chẵn thì

  • sp:=A [0]

  • for i:=1 to length of A - 1

    • nếu A [i]> 0, thì sp:=tối thiểu của sp và A [i]

  • trả về tổng các phần tử của A - (2 * sp)

• nếu không, trả về tổng các phần tử của A

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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))

Đầu vào

[3,-1,0,2]
3

Đầu ra

6