সমস্যা বিবরণ
একটি অ্যারে দেওয়া আছে। অ্যারেতে সর্বোচ্চ দুটি এলিমেন্টের চিহ্ন ইনভার্ট (পজিটিভকে 네가েটিভ ও 네가েটিভকে পজিটিভ) করে সর্বোচ্চ সাবঅ্যারে যোগফল বের করতে হবে।
উদাহরণ
ইনপুট - অ্যারে = {-5, 1, 3, 8, -2, 4, 7}
আউটপুট - 30
ব্যাখ্যা - ইনডেক্স ০ থেকে ৬ পর্যন্ত এলিমেন্ট নেওয়া হয়েছে এবং -5 ও -2-এর চিহ্ন ইনভার্ট করলে সর্বোচ্চ যোগফল ৩০ পাওয়া যায়।
সমাধানের পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করে প্রতিটি সাবঅ্যারের আকার ১ থেকে n পর্যন্ত সর্বোচ্চ যোগফল বের করা হয়। প্রতিটি সাবঅ্যারেতে তিনটি কেস বিবেচনা করা হয়:
- কেস ১: সাবঅ্যারেতে দুটি এলিমেন্ট ইনভার্ট করে সর্বোচ্চ যোগফল।
- কেস ২: সাবঅ্যারেতে একটি এলিমেন্ট ইনভার্ট করে সর্বোচ্চ যোগফল।
- কেস ৩: কোনো এলিমেন্ট ইনভার্ট না করে সর্বোচ্চ যোগফল।
এই মানগুলো maxSum নামে ২D অ্যারেতে সংরক্ষণ করা হয় এবং সবচেয়ে বড় মানটি রিটার্ন করা হয়।
C++ কোড উদাহরণ
#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
