Tối đa hóa tổng mảng sau K lần đổi dấu trong Python

Cho mảng A các số nguyên. Ta sửa đổi mảng như sau: chọn index i và thay A[i] bằng -A[i], lặp lại K lần. Trả về tổng lớn nhất có thể của mảng sau K lần thay đổi.

Ví dụ: A = [4,2,3], K = 1 → output 5. Chọn index 1, mảng thành [4,-2,3].

Giải pháp:

• Sắp xếp mảng A
• for i từ 0 đến len(A)-1
  • nếu A[i] < 0: A[i] = -A[i], K -= 1
  • nếu K == 0: break
• nếu K chẵn:
  • sp := A[0]
  • for i từ 1 đến len(A)-1
    • nếu A[i] > 0: sp = min(sp, A[i])
  • trả về sum(A) - 2*sp
• ngược lại: trả về sum(A)

Ví dụ (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))

Input

[3, -1, 0, 2] 3

Output

6