সমস্যা বিবরণ
N ইন্টিজারের একটি অ্যারে arr[] দেওয়া আছে। কাজ হল প্রথমে সর্বোচ্চ সাব-অ্যারে যোগফল বের করা এবং তারপর সাব-অ্যারে থেকে সর্বোচ্চ একটি উপাদান সরানো। সর্বোচ্চ একটি উপাদান সরাতে হবে যাতে সরানোর পর সর্বোচ্চ যোগফল সর্বাধিক হয়।
যদি দেওয়া ইনপুট অ্যারে হয় {1, 2, 3, -2, 3} তবে সর্বোচ্চ সাব-অ্যারে যোগফল হয় {2, 3, -2, 3}। তারপর আমরা -2 সরাতে পারি। সরানোর পর বাকি অ্যারে হয়:
{1, 2, 3, 3} যার যোগফল ৯ যা সর্বোচ্চ।
অ্যালগরিদম
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
