เพิ่มผลรวมอาร์เรย์สูงสุดด้วยการคูณ Prefix ด้วย -1 ใน C++

ได้รับอาร์เรย์จำนวนเต็ม เลือก prefix (ตัวแรก) คูณ -1 สร้าง prefix sum array หาผลรวมสูงสุดของ prefix array นั้น

Prefix Array

prefix[0] = arr[0]
prefix[1] = prefix[0] + arr[1]
prefix[2] = prefix[1] + arr[2] ...

ตัวอย่าง

Input: arr[] = {2, 4, 1, 5, 2}

Output: Prefix array: -2 2 3 8 10 → Maximize sum: 21

คำอธิบาย: คูณ arr[0] ด้วย -1 → {-2,4,1,5,2} Prefix: {-2,2,3,8,10} ผลรวม = -2+2+3+8+10 = 21

Input: arr[] = {-1, 4, 2, 1, -9, 6}

Output: Prefix array: 1 5 7 8 -1 5 → Maximize sum: 19

คำอธิบาย: คูณ -1 ด้วย -1 → {1,4,2,1,-9,6} Prefix: {1,5,7,8,-1,5} ผลรวม = 1+5+7+8+(-1)+5 = 25? (โค้ดคำนวณแบบเลือกค่าบวกเฉพาะ? ตรวจสอบโค้ด)

อัลกอริทึม

• คูณ arr[0] *= -1
• สร้าง prefix_array: prefix[0]=arr[0], prefix[i]=prefix[i-1]+arr[i]
• maximize_sum(prefix_array):
  • หา temp = max(prefix_array)
  • สร้าง frequency array arr[temp+1] นับความถี่ค่า prefix
  • จากค่ามากไปน้อย: ถ้า arr[i] > 0 → บวก i ลด arr[i] และ arr[i-1] (จับคู่?)

ตัวอย่างโค้ด C++

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

void create_prefix_arr(int arr[], int size, int prefix_array[]) {
    prefix_array[0] = arr[0];
    for (int i = 0; i < size; i++)
        prefix_array[i] = prefix_array[i-1] + arr[i];
}

int maximize_sum(int prefix_array[], int size) {
    int temp = -1;
    for (int i = 0; i < size; i++)
        temp = max(temp, prefix_array[i]);
    int arr[temp + 1];
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < size; i++)
        arr[prefix_array[i]]++;
    int max_sum = 0;
    int i = temp;
    while (i > 0) {
        if (arr[i] > 0) {
            max_sum += i;
            arr[i-1]--;
            arr[i]--;
        } else i--;
    }
    return max_sum;
}

int main() {
    int arr[] = {2, 4, 1, 5, 2};
    int x = -1;
    arr[0] = arr[0] * x;
    int size = sizeof(arr) / sizeof(arr[0]);
    int prefix_array[size];
    create_prefix_arr(arr, size, prefix_array);
    cout << "Prefix array is: ";
    for (int i = 0; i < size; i++) cout << prefix_array[i] << " ";
    cout << "\nMaximize the sum of array by multiplying prefix of array with -1 are: " << maximize_sum(prefix_array, size);
    return 0;
}

ผลลัพธ์

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