เพิ่ม Maximum Subarray Sum หลังลบได้สูงสุด 1 องค์ประกอบใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ขนาด N จำนวนเต็ม งานคือหา Maximum Subarray Sum ก่อน แล้วลบได้สูงสุด 1 องค์ประกอบจาก Subarray นั้น ลบได้สูงสุด 1 ตัว เพื่อให้ผลรวมสูงสุดหลังลบมีค่ามากที่สุด

ถ้าอินพุตอาร์เรย์คือ {1, 2, 3, -2, 3} Maximum Subarray Sum คือ {2, 3, -2, 3} แล้วเราลบ -2 อาร์เรย์ที่เหลือกลายเป็น

{1, 2, 3, 3} ผลรวม 9 ซึ่งเป็นค่าสูงสุด

อัลกอริทึม

1. ใช้ Kadane's Algorithm หา Maximum Subarray Sum
2. เมื่อหาผลรวมได้แล้ว ใช้ Kadane's Algorithm อีกครั้งเพื่อหาผลรวมสูงสุดอีกครั้ง (ด้วยการปรับเปลี่ยนเล็กน้อย)

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

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

int getMaxSubarraySum(int* arr, int n) {
    int max = INT_MIN;
    int currentMax = 0;
    for (int i = 0; i < n; ++i) {
        currentMax = currentMax + arr[i];
        if (max < currentMax) {
            max = currentMax;
        }
        if (currentMax < 0) {
            currentMax = 0;
        }
    }
    return max;
}

int getMaxSum(int* arr, int n) {
    int cnt = 0;
    int minVal = INT_MAX;
    int minSubarr = INT_MAX;
    int sum = getMaxSubarraySum(arr, n);
    int max = INT_MIN;
    int currentMax = 0;
    for (int i = 0; i < n; ++i) {
        currentMax = currentMax + arr[i];
        ++cnt;
        minSubarr = min(arr[i], minSubarr);
        if (sum == currentMax) {
            if (cnt == 1) {
                minVal = min(minVal, 0);
            } else {
                minVal = min(minVal, minSubarr);
            }
        }
        if (currentMax < 0) {
            currentMax = 0;
            cnt = 0;
            minSubarr = INT_MAX;
        }
    }
    return sum - minVal;
}

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

ผลลัพธ์

Maximum sum = 9