এই সমস্যা, আমরা একটি অ্যারে দেওয়া হয়. আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা c++ এ সর্বাধিক একটি উপাদান অপসারণ করে সর্বাধিক যোগফল সাব্যারে খুঁজে পাবে।
মূলত, আমাদের এমন একটি উপাদান খুঁজে বের করতে হবে যা সরানো হলে অ্যারেতে থাকা উপাদানগুলির জন্য সর্বাধিক যোগফল প্রদান করে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={5, 1, 9, 2, -1, 7}
আউটপুট − 24
ব্যাখ্যা − আমরা অ্যারে থেকে -1 সরিয়ে দিয়েছি এবং যোগফল সব সম্ভাব্য ফলাফলের সর্বোচ্চ হয়ে উঠেছে।
এই সমস্যার একটি সমাধান হবে অ্যারের ন্যূনতম উপাদান খুঁজে বের করা এবং তারপর অ্যারের বাকি সমস্ত উপাদানের যোগফল খুঁজে বের করা।
কিন্তু এখানে, উপাদান অপসারণ শর্ত প্রয়োগ করা হয় না, কাদানের অ্যালগরিদম একটি ভাল উপায়ে সমস্যা সমাধান করবে। সুতরাং, এখানে আমরা সর্বাধিক যোগফল এমনভাবে গণনা করব যাতে আমরা শুরু থেকে এবং শেষ থেকে ith উপাদান পর্যন্ত যোগফল খুঁজে পাব।
এবং তারপরে শুরু এবং শেষ যোগ অ্যারে ব্যবহার করে কোন 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
