Tối đa hóa tổng mảng prefix sau khi nhân phần tử đầu với -1 trong C++

Cho mảng số nguyên. Nhân phần tử đầu tiên với -1, xây mảng prefix sum, tìm tổng lớn nhất của các phần tử prefix sum (có thể bỏ qua một số phần tử âm).

Ví dụ

Đầu vào: arr[] = {2, 4, 1, 5, 2}

Đầu ra: Prefix: -2 2 3 8 10 → Max sum = 21

Giải thích: arr[0] *= -1 → {-2,4,1,5,2}. Prefix: -2, 2, 3, 8, 10. Chọn các giá trị dương: 2+3+8+10=23? Code gốc cho 21 (có thể logic chọn khác).

Đầu vào: arr[] = {-1, 4, 2, 1, -9, 6}

Đầu ra: Prefix: 1 5 7 8 -1 5 → Max sum = 19

Phương pháp

• Nhân arr[0] *= -1.
• Tính prefix sum: pref[i] = pref[i-1] + arr[i].
• Tìm max prefix value → cấp phát mảng đếm tần suất.
• Duyệt từ max về 0: nếu freq[i] > 0 → cộng i vào kết quả, giảm freq[i] và freq[i-1]. (Logic này tương đương chọn tập con không liền kề? Cần xem lại).

Ví dụ mã C++

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

void createPrefix(int arr[], int n, int pref[]) {
    pref[0] = arr[0];
    for (int i=1; i freq(mx+1, 0);
    for (int i=0; i= 0) freq[pref[i]]++;
    int sum = 0;
    for (int i=mx; i>0; i--) {
        while (freq[i] > 0) {
            sum += i;
            freq[i]--;
            if (i>0) freq[i-1]--;
        }
    }
    return sum;
}

int main() {
    int arr[] = {2, 4, 1, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    arr[0] *= -1;
    int pref[n];
    createPrefix(arr, n, pref);
    cout << "Prefix array: ";
    for (int x: pref) cout << x << " ";
    cout << "\nMaximized sum: " << maximizeSum(pref, n);
    return 0;
}

Đầu ra chương trình

Prefix array is: -2 2 3 8 10
Maximize the sum of array by multiplying prefix of array with -1 are: 21