เพิ่มผลรวมอาร์เรย์หลัง K ครั้ง Negation ใน C++

โจทย์

ได้รับอาร์เรย์ขนาด n และตัวเลข k ต้องปรับเปลี่ยนอาร์เรย์ k ครั้ง

ปรับเปลี่ยนหมายถึงในแต่ละครั้ง เราสามารถแทนที่องค์ประกอบ arr[i] ด้วยการ Negate คือ arr[i] = -arr[i] งานคือทำการดำเนินการนี้เพื่อให้หลัง k ครั้ง ผลรวมของอาร์เรย์ต้องสูงสุด

ถ้าอินพุต arr[] = {7, -3, 5, 4, -1} ผลรวมสูงสุดคือ 20

• Negate -3 ก่อน อาร์เรย์กลายเป็น {7, 3, 5, 4, -1}
• Negate -1 อาร์เรย์กลายเป็น {7, 3, 5, 4, 1}

อัลกอริทึม

1. แทนที่ Minimum Element arr[i] ในอาร์เรย์ด้วย -arr[i] สำหรับการดำเนินการปัจจุบัน
2. เมื่อ Minimum Element กลายเป็น 0 ไม่ต้องทำอะไรเพิ่มเติม ด้วยวิธีนี้ เราสามารถทำให้ผลรวมอาร์เรย์สูงสุดหลัง K ครั้ง

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

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

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

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

ผลลัพธ์

Maximum sum = 20