Tối đa hóa tổng mảng bằng phép đảo dấu chính xác n phần tử trong C++

Đề bài

Cho mảng kích thước (2n-1). Mỗi phép toán chọn chính xác n phần tử và đổi dấu (nhân -1). Lặp lại phép toán bất kỳ số lần. Tìm tổng lớn nhất có thể.

Ví dụ: {-2,100,-3}, n=2. Đổi dấu -2 và -3 → {2,100,3}, tổng=105.

Thuật toán

1. Đếm số phần tử âm (negCnt).
2. Tính tổng giá trị tuyệt đối (sum).
3. Tìm giá trị tuyệt đối nhỏ nhất (m).
4. Nếu negCnt lẻ VÀ n chẵn → phải để lại một số âm nhỏ nhất → kết quả = sum - 2*m.
5. Ngược lại → kết quả = sum.

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

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

int getMaxSum(int* arr, int n) {
    int negCnt = 0;
    int sum = 0;
    int m = INT_MAX;
    for (int i = 0; i < 2*n - 1; ++i) {
        if (arr[i] < 0) ++negCnt;
        sum += abs(arr[i]);
        m = min(m, abs(arr[i]));
    }
    if (negCnt % 2 == 1 && n % 2 == 0) sum -= 2 * m;
    return sum;
}

int main() {
    int arr[] = {-2, 100, -3};
    int n = 2;
    cout << "Tong lon nhat = " << getMaxSum(arr, n) << endl;
    return 0;
}

Kết quả

Tong lon nhat = 105