একটি অ্যারে দেওয়া আছে। সর্বোচ্চ একটি এলিমেন্ট রিমুভ করে ম্যাক্সিমাম সাবঅ্যারে সাম বের করতে হবে।
উদাহরণ: array = {5, 1, 9, 2, -1, 7} -> আউটপুট: ২৪ ( -1 রিমুভ করলে ম্যাক্সিমাম সাম)।
সহজ সমাধান: মিনিমাম এলিমেন্ট বাদ দিয়ে বাকি সাম। কিন্তু ক্যাডেনস অ্যালগরিদম (Kadane's algorithm) দিয়ে ভালো সমাধান: স্টার্ট থেকে i-তম এলিমেন্ট পর্যন্ত ম্যাক্স সাম (startSum) এবং এন্ড থেকে i-তম এলিমেন্ট পর্যন্ত ম্যাক্স সাম (endSum) ক্যালকুলেট করিয়ে i-তম এলিমেন্ট স্কিপ করলে সাম = startSum[i-1] + endSum[i+1]। সবচেয়ে বড় সাম বের করব।
উদাহরণ
#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
