C++ में अधिकतम K सरणी तत्वों के संकेतों को फ़्लिप करके अधिकतम सबअरे योग

इस समस्या में, हमें एक सरणी और एक पूर्णांक k दिया जाता है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो C++ में अधिकतम k सरणी तत्वों के चिह्नों को फ़्लिप करके अधिकतम सबअरे योग प्राप्त करेगा।

कोड विवरण - यहां, हमें सरणी में फ़्लिप करने के लिए अधिक से अधिक k तत्वों को खोजना होगा जो इस सरणी से बनाए गए सबअरे के योग को अधिकतम बना देगा।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - सरणी ={1, -2, 7, 0} k =2

आउटपुट -10

स्पष्टीकरण - हम केवल एक तत्व फ्लिप करेंगे जो -2 है, यह सरणी योग 10 बनाता है जो अधिकतम संभव है।

इस समस्या को हल करने के लिए, हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे जो i ^th से सरणी का अधिकतम संभव योग प्राप्त करेगा। सूचकांक से j ^वें अनुक्रमणिका और इसे एक सरणी 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