हमें एक पूर्णांक सरणी और एक पूर्णांक वेरिएबल यानी 'X' दिया गया है। कार्य पहले दी गई सरणी से उपसरणी बनाना है और फिर उपसरणी के सभी तत्वों को पूर्णांक X से गुणा करना है। अंत में उन तत्वों को ढूंढें जो अधिकतम योग में योगदान देंगे।
विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:
इनपुट: int arr[] = {2, 4, 1, -5, -2}, X = 3
आउटपुट: किसी भी उपसरणी के सभी तत्वों को X से गुणा करने के बाद उपसरणी योग को अधिकतम करें: 21
व्याख्या: हमें एक सरणी और एक पूर्णांक वेरिएबल X दिया गया है। पहले, दी गई सरणी से उपसरणी लें, मान लीजिए {2, 4, 1}। अब उपसरणी के सभी तत्वों को X यानी 3 से गुणा करें तो सरणी {6, 12, 3, -5, -2} बन जाएगी। अंत में, अधिकतम उपसरणी योग की जांच करें जो 6 + 12 + 3 = 21 द्वारा लौटाया जाएगा।
इनपुट: int arr[] = {-1, 2, -6, 3, -4}, x = -1
आउटपुट: किसी भी उपसरणी के सभी तत्वों को X से गुणा करने के बाद उपसरणी योग को अधिकतम करें: 11
व्याख्या: हमें एक सरणी और एक पूर्णांक वेरिएबल X दिया गया है। पहले, दी गई सरणी से उपसरणी लें, मान लीजिए {-1, -6, -4}। अब उपसरणी के सभी तत्वों को X यानी -1 से गुणा करें तो सरणी {1, 2, 6, 3, 4} बन जाएगी। अंत में, अधिकतम उपसरणी योग की जांच करें जो 1 + 6 + 4 = 11 द्वारा लौटाया जाएगा।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:
- एक पूर्णांक सरणी और एक पूर्णांक वेरिएबल 'X' इनपुट करें। सरणी का आकार गणना करें और डेटा को फंक्शन Max_Subarray(arr, size, x) में पास करें।
- फंक्शन Max_Subarray(arr, size, x) के अंदर:
- int arr_2[size][3] के रूप में एक सरणी घोषित करें और एक अस्थायी वेरिएबल temp को 0 पर सेट करें।
- C++ में memset() विधि का उपयोग करके सरणी 'arr_2' के सभी तत्वों को -1 से इनिशियलाइज़ करें।
- i को 0 से सरणी के आकार तक लूप चलाएं। अंदर, temp को फंक्शन max(temp, check(i, 0, arr, arr_2, size, x)) कॉल पर सेट करें।
- temp लौटाएं।
- फंक्शन int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) के अंदर:
- count नामक एक अस्थायी वेरिएबल को 0 पर घोषित करें।
- जांचें यदि first = size तो 0 लौटाएं।
- जांचें यदि arr_2[first][last] != -1 तो arr_2[first][last] लौटाएं।
- जांचें यदि last = 0 तो C++ के इनबिल्ट max फंक्शन को कॉल करके अधिकतम मान ढूंढें: max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x)) और count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) भी सेट करें।
- अन्यथा यदि last = 1 जांचें तो count को max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) पर सेट करें और count को max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) पर सेट करें।
- अन्यथा, count को max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) पर सेट करें।
- arr_2[first][last] को count पर लौटाएं।
- परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) {
int count = 0;
if (first == size) {
return 0;
}
if (arr_2[first][last] != -1) {
return arr_2[first][last];
}
if (last == 0) {
count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
} else if (last == 1) {
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
} else {
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
}
return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x) {
int arr_2[size][3];
int temp = 0;
memset(arr_2, -1, sizeof arr_2);
for(int i = 0; i < size; i++) {
temp = max(temp, check(i, 0, arr, arr_2, size, x));
}
return temp;
}
int main() {
int arr[] = {2, 4, 1, -5, -2};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout << "Maximize the subarray sum after multiplying all elements of any subarray with X are: " << Max_Subarray(arr, size, x);
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Maximize the subarray sum after multiplying all elements of any subarray with X are: 21
