Chương trình tìm tổng lớn nhất sau tối đa k phép đổi dấu trong Python

Cho danh sách nums và số k. Mỗi phép toán chọn một phần tử và đổi dấu (nhân -1). Phải thực hiện đúng k phép. Tìm tổng lớn nhất có thể đạt được.

Ví dụ: nums = [2, 1, -6, -2], k = 3 → kết quả 9. Đổi dấu -6, -2, 1 → [2, -1, 6, 2], tổng = 9.

Thuật toán giải quyết (Tham lam + Sắp xếp)

1. Sắp xếp nums tăng dần
2. Duyệt từ nhỏ đến lớn: nếu phần tử âm và k > 0, đổi dấu, giảm k
3. Sau khi hết số âm hoặc hết k:
   • Nếu k lẻ: phải đổi dấu một lần nữa → trừ đi 2 * min(nums) từ tổng
   • Nếu k chẵn: đổi dấu cặp nhau không thay đổi tổng
4. Trả về tổng

Ví dụ minh họa

def solve(nums, k):
    n = len(nums)
    if n == 0:
        return 0
    nums.sort()
    for idx in range(n):
        if nums[idx] < 0 and k > 0:
            k -= 1
            nums[idx] *= -1
    if k & 1 == 1:
        return sum(nums) - 2 * min(nums)
    return sum(nums)

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

Đầu vào

[2, 1, -6, -2], 3

Đầu ra

9