এই সমস্যায়, আমাদের একটি অ্যারে এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা C++-এ সর্বাধিক k অ্যারে উপাদানগুলির চিহ্ন ফ্লিপ করে সর্বাধিক সাব্যারে যোগফল খুঁজে পাবে।
কোডের বিবরণ − এখানে, অ্যারেতে ফ্লিপ করার জন্য আমাদের সর্বাধিক k উপাদান খুঁজে বের করতে হবে যা এই অ্যারে থেকে তৈরি সাবয়ারের যোগফলকে সর্বোচ্চ করে তুলবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={1, -2, 7, 0} k =2
আউটপুট − 10
ব্যাখ্যা − আমরা শুধুমাত্র একটি উপাদান ফ্লিপ করব যা হল -2, এটি অ্যারের যোগফল 10 তৈরি করে যা সর্বাধিক সম্ভব।
এই সমস্যা সমাধানের জন্য, আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব যা i th থেকে অ্যারের সর্বাধিক সম্ভাব্য যোগফল খুঁজে পাবে j th তে সূচক সূচক করুন এবং এটিকে একটি অ্যারেতে সংরক্ষণ করুন maxSumij[i][j] এবং উভয় ক্ষেত্রেই বিবেচনা করুন যদি এলিমেন্ট ফ্লিপ করা হয় বা এলিমেন্ট ফ্লিপ ছাড়াই এটি সেরা-কেস ফিরিয়ে দেবে, এটি ফাংশনে একটি পুনরাবৃত্ত কল ব্যবহার করে করা হবে। শেষ পর্যন্ত, আমরা maxSumij[i][j] ম্যাট্রিক্স থেকে সর্বাধিক উপাদান খুঁজে পাব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
if (flips > k)
return -1e9;
if (i == n)
return 0;
if (arraySumij[i][flips] != -1)
return arraySumij[i][flips];
int maxSum = 0;
maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
arraySumij[i][flips] = maxSum;
return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
memset(arraySumij, -1, sizeof(arraySumij));
int maxSum = -100;
for (int i = 0; i < n; i++)
maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
return maxSum;
}
int main() {
int a[] = {-3, 56, -1, 8};
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
cout<<"Maximum subarry sum by fipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
return 0;
} আউটপুট
Maximum subarry sum by fipping signs of at most 2 element is 66
