इस समस्या में, हमें एक सरणी दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम एक तत्व हटाकर अधिकतम योग उपसरणी ढूंढे।
मूल रूप से, हमें वह एक तत्व ढूंढना है जिसे हटाने पर सरणी में शेष तत्वों का योग अधिकतम हो।
आइए एक उदाहरण से समझते हैं:
इनपुट - सरणी = {5, 1, 9, 2, -1, 7}
आउटपुट - 24
व्याख्या - हमने सरणी से -1 को हटा दिया और योग सभी संभावित परिणामों का अधिकतम हो गया।
इस समस्या का एक समाधान सरणी के न्यूनतम तत्व को ढूंढना और फिर सरणी के शेष सभी तत्वों का योग निकालना होगा।
लेकिन यहां, तत्व हटाने की शर्त लागू नहीं होती, कडाने का एल्गोरिदम (Kadane's algorithm) इस समस्या को बेहतर तरीके से हल करेगा। तो, यहां हम इस तरह से अधिकतम योग की गणना करेंगे कि हम शुरुआत से i-वें तत्व तक का योग और अंत से भी योग ढूंढेंगे।
और फिर जांचेंगे कि कौन सा i-वां तत्व छोड़ने पर शुरुआत और अंत के योग सरणियों का उपयोग करके अधिकतम योग देता है और फिर दिए गए तत्व को छोड़ने के बाद योग प्रिंट करेंगे।
उदाहरण
#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 << "एक तत्व हटाने के बाद अधिकतम उपसरणी योग है " << maxSubarraySum(array, n);
return 0;
}
आउटपुट
एक तत्व हटाने के बाद अधिकतम उपसरणी योग है 28
