home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

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

โจทย์ปัญหา

ได้รับอาร์เรย์ ให้หาผลรวมเซิร์บอาร์เรย์สูงสุดหลังจากกลับเครื่องหมาย (invert) ขององค์ประกอบได้สูงสุด 2 ตัว

ตัวอย่าง

นำเข้า: array = {-5, 1, 3, 8, -2, 4, 7}
ผลลัพธ์: 30
คำอธิบาย: เลือกเซิร์บอาร์เรย์ทั้งหมด (index 0-6) และกลับเครื่องหมาย -5 และ -2 ให้เป็น 5 และ 2 ผลรวม = 5+1+3+8+2+4+7 = 30

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

ใช้ตาราง DP 3 มิติ maxSum[i][j] โดย:

  • i = ตำแหน่งในอาร์เรย์ (1-indexed)
  • j = จำนวนครั้งที่กลับเครื่องหมายแล้ว (0, 1, หรือ 2)
  • maxSum[i][j] = ผลรวมสูงสุดของเซิร์บอาร์เรย์ที่จบที่ตำแหน่ง i โดยใช้การกลับเครื่องหมาย j ครั้ง

สมการเรียกซ้ำ (Recurrence):

  • Case 0 (ไม่กลับ): maxSum[i][0] = max(arr[i], maxSum[i-1][0] + arr[i])
  • Case 1 (กลับ 1 ครั้ง): maxSum[i][1] = max(0, maxSum[i-1][0]) - arr[i] (เริ่มใหม่หรือต่อจาก case 0)
    ถ้า i ≥ 2: maxSum[i][1] = max(maxSum[i][1], maxSum[i-1][1] + arr[i])
  • Case 2 (กลับ 2 ครั้ง): ถ้า i ≥ 2: maxSum[i][2] = maxSum[i-1][1] - arr[i]
    ถ้า i ≥ 3: maxSum[i][2] = max(maxSum[i][2], maxSum[i-1][2] + arr[i])

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

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

int findMaxSubarraySum(int a[], int n) {
    int maxSubarraySum = 0;
    int* arr = new int[n + 1];
    for (int i = 1; i <= n; i++) arr[i] = a[i - 1];

    int** maxSum = new int*[n + 1];
    for (int i = 0; i <= n; i++) maxSum[i] = new int[3];

    for (int i = 1; i <= n; ++i) {
        maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
        maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
        if (i >= 2) maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
        if (i >= 2) maxSum[i][2] = maxSum[i - 1][1] - arr[i];
        if (i >= 3) maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);

        maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
    }
    return maxSubarraySum;
}

int main() {
    int arr[] = {-5, 1, 3, 8, -2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray sum after inverting at most two elements is "
         << findMaxSubarraySum(arr, n);
    return 0;
}

ผลลัพธ์

Maximum subarray sum after inverting at most two elements is 30

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

วิธีนี้เป็น Bottom-up DP ที่มีความซับซ้อน O(n) เวลา และ O(n) พื้นที่ (สามารถลดเป็น O(1) ได้โดยเก็บแค่แถวก่อนหน้า) เหมาะสำหรับกรณีที่จำกัดจำนวนการกลับเครื่องหมายไว้ต่ำ (เช่น 2 ครั้ง)