इस समस्या में, हमें एक सरणी दी जाती है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो c++ में अधिकतम एक तत्व को हटाते हुए अधिकतम योग सबएरे को खोजेगा।
मूल रूप से, हमें एक ऐसे तत्व को खोजने की आवश्यकता है जो हटाए जाने पर सरणी में शेष तत्वों के लिए अधिकतम योग प्रदान करता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी ={5, 1, 9, 2, -1, 7}
आउटपुट - 24
स्पष्टीकरण - हमने सरणी से -1 हटा दिया है और योग सभी संभावित परिणामों में से अधिकतम बन गया है।
इस समस्या का एक समाधान यह होगा कि सरणी का न्यूनतम तत्व खोजा जाए और फिर सरणी के सभी शेष तत्वों का योग ज्ञात किया जाए।
लेकिन यहां एलिमेंट रिमूवल कंडीशन लागू नहीं है, कडाने का एल्गोरिथम बेहतर तरीके से समस्या का समाधान करेंगे। इसलिए, यहां हम अधिकतम योग की गणना इस तरह करेंगे कि हम शुरुआत से लेकर अंत तक के तत्व तक का योग पाएंगे।
और फिर जाँच करें कि प्रारंभ और समाप्ति योग सरणियों का उपयोग करते समय कौन सा ith तत्व छोड़ दिया गया है और फिर दिए गए तत्व को छोड़ने के बाद योग को प्रिंट करें।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
#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