इस समस्या में, हमें एक सरणी और एक पूर्णांक k दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम k सरणी तत्वों के चिह्न बदलकर अधिकतम सबएरे सम ढूंढेगा।
कोड विवरण - यहां, हमें सरणी में अधिकतम k तत्व ढूंढने होंगे जिन्हें पलटने से इस सरणी से बने सबएरे का सम अधिकतम हो जाएगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी = {1, -2, 7, 0} k = 2
आउटपुट - 10
व्याख्या - हम केवल एक तत्व -2 को पलटेंगे, जिससे सरणी का सम 10 हो जाता है जो अधिकतम संभव है।
इस समस्या को हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे जो i-वें इंडेक्स से 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
