সর্বোচ্চ k সংখ্যক এলিমেন্টের চিহ্ন ফ্লিপ করে সর্বোচ্চ সাবঅ্যারে যোগফল C++-এ

সমস্যা বিবরণ

একটি অ্যারে এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। অ্যারেতে সর্বোচ্চ k সংখ্যক এলিমেন্টের চিহ্ন (পজিটিভ/নেগেটিভ) পরিবর্তন করে সর্বোচ্চ সাবঅ্যারে যোগফল বের করতে হবে।

উদাহরণ

ইনপুট - অ্যারে = {1, -2, 7, 0}, k = 2

আউটপুট - 10

ব্যাখ্যা - কেবল -2-এর চিহ্ন ফ্লিপ করলে অ্যারে হয় {1, 2, 7, 0} এবং যোগফল ১০, যা সর্বোচ্চ সম্ভব।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমাধান করা হয়েছে। maxSumij[i][j] ম্যাট্রিক্সে i-তম ইনডেক্স থেকে j-তম ফ্লিপ পর্যন্ত সর্বোচ্চ যোগফল সংরক্ষণ করা হয়। রিকার্সিভ ফাংশন কল দিয়ে উভয় পরিস্থিতি (ফ্লিপ করা হয়েছে বা নয়) বিবেচনা করে সর্বোত্তম সমাধান বের করা হয়। শেষে ম্যাট্রিক্স থেকে সর্বোচ্চ মান বের করা হয়।

C++ কোড উদাহরণ

#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