ผลรวมเซิร์บอาร์เรย์สูงสุดจากการกลับเครื่องหมายสูงสุด K องค์ประกอบใน C++

โจทย์ปัญหา

ได้รับอาร์เรย์และจำนวนเต็ม k ให้หาผลรวมเซิร์บอาร์เรย์สูงสุดที่เป็นไปได้ โดยอนุญาตให้กลับเครื่องหมาย (บวก↔ลบ) ขององค์ประกอบได้สูงสุด k ตัว

ตัวอย่าง

นำเข้า: array = {1, -2, 7, 0}, k = 2
ผลลัพธ์: 10
คำอธิบาย: กลับเครื่องหมาย -2 ให้เป็น 2 ทำให้อาร์เรย์กลายเป็น {1, 2, 7, 0} ผลรวม = 10

แนวคิดการแก้ปัญหา (Dynamic Programming)

ใช้ตาราง DP ขนาด dp[i][flips] แทนผลรวมสูงสุดที่ได้จากตำแหน่ง i ไปจนจบ โดยใช้การกลับเครื่องหมายไปแล้ว flips ครั้ง

• State: dp[i][flips] = ผลรวมสูงสุดจาก index i ถึงสิ้นสุด โดยกลับเครื่องหมายไปแล้ว flips ครั้ง
• Transition: ที่แต่ละตำแหน่ง มี 2 ทางเลือก:
  • ไม่กลับเครื่องหมาย: a[i] + dp[i+1][flips]
  • กลับเครื่องหมาย (ถ้า flips < k): -a[i] + dp[i+1][flips+1]
• Base Case: ถ้า i == n คืนค่า 0; ถ้า flips > k คืนค่า -infinity

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

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

#define MAX_N 100
#define MAX_K 10

int dp[MAX_N][MAX_K];

int findSubarraySum(int i, int flips, int n, int a[], int k) {
    if (flips > k) return -1e9;
    if (i == n) return 0;
    if (dp[i][flips] != -1) return dp[i][flips];

    int maxSum = 0;
    // ไม่กลับเครื่องหมาย
    maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
    // กลับเครื่องหมาย
    maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));

    dp[i][flips] = maxSum;
    return maxSum;
}

int maxSubarraySumFlip(int a[], int n, int k) {
    memset(dp, -1, sizeof(dp));
    int maxSum = -100;
    for (int i = 0; i < n; i++)
        maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
    return maxSum;
}

int main() {
    int a[] = {-3, 56, -1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 2;
    cout << "Maximum subarray sum by flipping signs of at most "
         << k << " element is " << maxSubarraySumFlip(a, n, k);
    return 0;
}

ผลลัพธ์

Maximum subarray sum by flipping signs of at most 2 element is 66

คำอธิบายเพิ่มเติม

วิธีนี้ใช้ Memoization (Top-down DP) เพื่อหลีกเลี่ยงการคำนวณซ้ำ ความซับซ้อนด้านเวลาเป็น O(n × k) และพื้นที่ O(n × k) เหมาะสำหรับ k ที่ไม่ใหญ่มาก