การหาผลรวมสูงสุดของอาร์เรย์หลังจากเปลี่ยนเครื่องหมายตามจำนวน k ครั้งใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มบวกและลบ พร้อมกับจำนวน K เป้าหมายคือการหาผลรวมสูงสุดของอาร์เรย์หลังจากทำการเปลี่ยนเครื่องหมายของสมาชิกในอาร์เรย์ทั้งหมด K ครั้ง โดยการดำเนินการเปลี่ยนเครื่องหมายแต่ละครั้งจะคูณสมาชิกใดสมาชิกหนึ่งด้วย -1

แนวคิดการแก้ปัญหา

วิธีการคือการแปลงจำนวนลบทั้งหมดให้เป็นจำนวนบวกก่อน หากมีจำนวนลบทั้งหมด N ตัว เราจะเรียงลำดับอาร์เรย์ จากนั้นพิจารณากรณีต่างๆ ดังนี้

• กรณี N < K: หลังจากทำการเปลี่ยนเครื่องหมาย N ครั้ง ทุกสมาชิกจะกลายเป็นจำนวนบวก และเหลือการดำเนินการอีก K-N ครั้ง

• ถ้า K-N เป็นเลขคู่: การเปลี่ยนเครื่องหมายซ้ำๆ จะไม่มีผลต่อผลรวม (เพราะคูณ -1 สองครั้งจะกลายเป็นค่าเดิม) จึงไม่ต้องทำอะไร

• ถ้า K-N เป็นเลขคี่: ให้เปลี่ยนเครื่องหมายของจำนวนที่มีค่าน้อยที่สุด (ซึ่งจะกลายเป็นลบ) เพื่อให้ผลรวมสูงสุด

• กรณี N > K: ให้เปลี่ยนเครื่องหมายของจำนวนลบ K ตัวแรก (ที่มีค่าน้อยที่สุดหลังเรียงลำดับ) จากนั้นหาผลรวม จะได้ผลรวมสูงสุด

ตัวอย่าง

อินพุต

Arr[] = { 0, -2, 6, 4, 8, 2, -3 }, K = 4

เอาต์พุต

Maximum array sum is : 25

คำอธิบาย - การเปลี่ยนเครื่องหมาย 4 ครั้ง:

1. 0, 2, 6, 4, 8, 2, -3  (-2 กลายเป็น 2)
2. 0, 2, 6, 4, 8, 2, 3   (-3 กลายเป็น 3)
3. 0, -2, 6, 4, 8, 2, 3  (2 กลายเป็น -2)
4. 0, 2, 6, 4, 8, 2, 3   (-2 กลายเป็น 2)
ผลรวมสูงสุดคือ 25

อินพุตอีกตัวอย่าง

Arr[] = { -1, -2, -3, -4, -5, -6, -7 }, K = 4

เอาต์พุต

Maximum array sum is : 16

คำอธิบาย - เปลี่ยนเครื่องหมายจำนวนลบ 4 ตัวที่มีค่ามากที่สุด (คือ -7, -6, -5, -4) ให้กลายเป็นบวก

รายละเอียดการทำงานของโปรแกรม

• อาร์เรย์ Arr[] ใช้เก็บจำนวนเต็ม
• ตัวแปร size เก็บขนาดอาร์เรย์ และ K คือจำนวนครั้งที่ต้องเปลี่ยนเครื่องหมาย
• ฟังก์ชัน returnSum(int arr[], int n, int k) รับอาร์เรย์ ขนาด และ k แล้วคืนค่าผลรวมสูงสุดหลังทำการเปลี่ยนเครื่องหมาย k ครั้ง
• ขั้นตอน:
  1. เรียงลำดับอาร์เรย์ด้วย sort(arr, arr+n)
  2. วนลูปเปลี่ยนเครื่องหมายของสมาชิกที่เป็นลบ (เริ่มจากค่าน้อยที่สุด) จนกว่า k จะเป็น 0 หรือจบอาร์เรย์
  3. ถ้า k ยังเหลือ และเป็นเลขคี่ ให้หาค่าที่น้อยที่สุดในอาร์เรย์ (ซึ่งตอนนี้เป็นบวกทั้งหมด) แล้วเปลี่ยนเครื่องหมายมันอีกครั้ง
  4. ถ้า k เหลือเป็นเลขคู่ ไม่ต้องทำอะไร
  5. คำนวณผลรวมของอาร์เรย์ทั้งหมดและคืนค่า

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

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

int returnSum(int arr[], int n, int k) {
    // เรียงลำดับอาร์เรย์
    sort(arr, arr + n);
    
    // เปลี่ยนเครื่องหมายของสมาชิกที่เป็นลบ เริ่มจากค่าน้อยที่สุด
    for (int i = 0; i < n; i++) {
        if (k > 0 && arr[i] < 0) {
            arr[i] = arr[i] * -1;
            k--;
        }
    }
    
    // ถ้า k เหลือและเป็นเลขคี่ ให้เปลี่ยนเครื่องหมายของค่าน้อยที่สุดอีกครั้ง
    if (k % 2 == 1) {
        int min = arr[0];
        int pos = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] < min) {
                min = arr[i];
                pos = i;
            }
        }
        arr[pos] *= -1;
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}

int main() {
    int Arr[] = { -3, 4, -3, 6, 8 };
    int size = 5;
    int K = 4;
    cout << "Maximum array sum that can be obtained after exactly k changes: "
         << returnSum(Arr, size, K) << endl;
    return 0;
}

ผลลัพธ์

Maximum array sum that can be obtained after exactly k changes : 24