C++ में अधिकतम एक तत्व हटाकर अधिकतम सबएरे योग को अधिकतम करना

समस्या कथन

N पूर्णांकों का एक ऐरे arr[] दिया गया है। कार्य पहले अधिकतम सब-एरे योग ढूंढना है और फिर सब-एरे से अधिकतम एक तत्व हटाना है। अधिकतम एक तत्व हटाएं ताकि हटाने के बाद अधिकतम योग अधिकतम हो।

यदि दिया गया इनपुट ऐरे है {1, 2, 3, -2, 3} तो अधिकतम सब-एरे योग {2, 3, -2, 3} है। फिर हम -2 हटा सकते हैं। हटाने के बाद शेष ऐरे बन जाता है:

{1, 2, 3, 3} योग 9 के साथ जो अधिकतम है।

एल्गोरिदम

1. कडाने के एल्गोरिदम का उपयोग करके अधिकतम सबएरे योग ढूंढें।
2. एक बार योग मिल जाने पर, कुछ मामूली बदलावों के साथ कडाने के एल्गोरिदम को फिर से लागू करके अधिकतम योग फिर से ढूंढें।

उदाहरण

#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