এই সমস্যা, আমরা একটি অ্যারে দেওয়া হয়. আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা C++ এ সর্বাধিক দুটি উপাদানকে উল্টানোর পরে সর্বাধিক সাব্যারে যোগফল খুঁজে পাবে।
সমস্যা বর্ণনা − এখানে, আমাদেরকে এমন সাবঅ্যারে খুঁজে বের করতে হবে যা অ্যারের যেকোনো দুটি সংখ্যার চিহ্নকে উল্টাতে সর্বোচ্চ যোগফল তৈরি করবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={-5, 1, 3, 8, -2, 4, 7}
আউটপুট − 30
ব্যাখ্যা − সর্বাধিক যোগফল সহ অ্যারে পেতে আমরা সূচক 0 থেকে 6 এবং উল্টানো মান -5 এবং -2 পর্যন্ত উপাদানগুলি বিবেচনা করব৷
এই সমস্যা সমাধানের জন্য, আমরা একটি গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করব। আমরা 1 থেকে n (অ্যারের দৈর্ঘ্য) আকারের সমস্ত সাবয়ারের সর্বাধিক যোগফল পরীক্ষা করব। সুতরাং, প্রতিটি সাবয়ারের জন্য, আমাদের তিনটি ক্ষেত্রে আছে −
কেস1 − সাবয়ারের দুটি উপাদানকে উল্টানোর পর সাবয়ারের সর্বোচ্চ যোগফল।
কেস2 − সাবয়ারের একটি উপাদানকে উল্টানোর পর সাবয়ারের সর্বোচ্চ যোগফল৷
কেস3 − সাবয়ারের শূন্য উপাদানগুলিকে উল্টানোর পরে সাবয়ারের সর্বাধিক যোগফল৷
সুতরাং, আমাদের কাছে থাকা প্রতিটি পুনরাবৃত্তির জন্য, আমরা অ্যারের সর্বাধিক সর্বাধিক এবং বর্তমান উপাদানটি খুঁজে পাব এবং এটিতে সর্বাধিক শুরু করব৷
আমরা সর্বাধিক যোগফলকে maxSum নামে একটি 2D অ্যারেতে সংরক্ষণ করব। এবং চূড়ান্ত maxSum হল 2D অ্যারের সমস্ত উপাদানের সর্বোচ্চ।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
int maxSubarraySum = 0;
int* arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = a[i - 1];
int** maxSum = new int*[n + 1];
for (int i = 0; i <= n; i++)
maxSum[i] = new int[3];
for (int i = 1; i <= n; ++i) {
maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
if (i >= 2)
maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
if (i >= 2)
maxSum[i][2] = maxSum[i - 1][1] - arr[i];
if (i >= 3)
maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
}
return maxSubarraySum;
}
int main(){
int arr[] = {-5, 1, 3, 8, -2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
return 0;
} আউটপুট
Maximum subarray sum after inverting at most two elements is 30
