Maximum Sum Subarray Removing At Most One Element ใน C++

ภาพรวมปัญหา

มีอาร์เรย์ ต้องหาผลรวมสูงสุดของ Subarray โดยอนุญาตให้ลบสูงสุด 1 องค์ประกอบ

ตัวอย่าง: [5, 1, 9, 2, -1, 7] → ลบ -1 ได้ผลรวม 24

วิธีแก้ปัญหา (Kadane's Algorithm แบบปรับเปลี่ยน)

1. คำนวณ startSum[i] = max subarray sum สิ้นสุดที่ i (จากซ้าย)
2. คำนวณ endSum[i] = max subarray sum เริ่มต้นที่ i (จากขวา)
3. ลองข้ามแต่ละตำแหน่ง i: startSum[i-1] + endSum[i+1]
4. หาค่าสูงสุดจากทุกกรณี

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

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

int maxSubarraySum(int array[], int n){
    int startSum[n], endSum[n];
    int maxSum = array[0], overAllMax = array[0];
    startSum[0] = array[0];
    for (int i = 1; i < n; i++){
        maxSum = max(array[i], maxSum + array[i]);
        overAllMax = max(overAllMax, maxSum);
        startSum[i] = maxSum;
    }
    maxSum = endSum[n-1] = array[n-1];
    for (int i = n-2; i >= 0; i--){
        maxSum = max(array[i], maxSum + array[i]);
        overAllMax = max(overAllMax, maxSum);
        endSum[i] = maxSum;
    }
    int SubArraySum = overAllMax;
    for (int i = 1; i < n - 1; i++)
        SubArraySum = max(SubArraySum, startSum[i-1] + endSum[i+1]);
    return SubArraySum;
}

int main() {
    int array[] = {5, 7, 1, -1, 4, 2, 9};
    int n = sizeof(array) / sizeof(array[0]);
    cout << "The maximum subarray after removing one element is " << maxSubarraySum(array, n);
    return 0;
}

ผลลัพธ์

The maximum subarray after removing one element is 28