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

Đề bài

Cho mảng kích thước n và số K. Thực hiện K lần: chọn một phần tử và đổi dấu (arr[i] = -arr[i]). Tối đa hóa tổng mảng sau K phép toán.

Ví dụ: {7,-3,5,4,-1}, K=2 → đổi -3 và -1 → {7,3,5,4,1} tổng=20.

Thuật toán tham lam

1. Lặp K lần: tìm phần tử nhỏ nhất (most negative), đổi dấu nó.
2. Nếu phần tử nhỏ nhất là 0 → dừng sớm (đổi dấu 0 không thay đổi tổng).

Độ phức tạp O(K*n). Có thể tối ưu O(n log n) bằng priority queue (min-heap).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int* arr, int n, int k) {
    for (int op = 0; op < k; ++op) {
        int minVal = INT_MAX, idx = -1;
        for (int i = 0; i < n; ++i)
            if (arr[i] < minVal) { minVal = arr[i]; idx = i; }
        if (minVal == 0) break;
        arr[idx] = -arr[idx];
    }
    int sum = 0;
    for (int i = 0; i < n; ++i) sum += arr[i];
    return sum;
}

// Phiên bản tối ưu O(n log k) với priority_queue
int getMaxSumOptimized(int* arr, int n, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; ++i) pq.push(arr[i]);
    while (k-- && !pq.empty()) {
        int x = pq.top(); pq.pop();
        if (x == 0) { pq.push(0); break; }
        pq.push(-x);
    }
    int sum = 0;
    while (!pq.empty()) { sum += pq.top(); pq.pop(); }
    return sum;
}

int main() {
    int arr[] = {7, -3, 5, 4, -1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Tong lon nhat = " << getMaxSum(arr, n, k) << endl;
    return 0;
}

Kết quả

Tong lon nhat = 20