हमें एक पूर्णांक सरणी दी गई है और कार्य पहले सरणी का उपसर्ग प्राप्त करना है और फिर इसे -1 से गुणा करना है, दूसरा सरणी का उपसर्ग योग गणना करना है और अंत में उत्पन्न उपसर्ग सरणी से अधिकतम योग ढूंढना है।
उपसर्ग सरणी इस प्रकार उत्पन्न होती है:
उपसर्गसरणी[0] का पहला तत्व = सरणी का पहला तत्व
उपसर्गसरणी[1] का दूसरा तत्व = उपसर्गसरणी[0] + arr[1]
उपसर्गसरणी[2] का तीसरा तत्व = उपसर्गसरणी[1] + arr[2]
उपसर्गसरणी[3] का चौथा तत्व = उपसर्गसरणी[2] + arr[3] ... आदि।
विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:
इनपुट: int arr[] = {2, 4, 1, 5, 2}
आउटपुट: उपसर्ग सरणी है: -2 2 3 8 10 सरणी के उपसर्ग को -1 से गुणा करके सरणी के योग को अधिकतम करें: 21
व्याख्या: हमें एक पूर्णांक सरणी दी गई है। तो हम पहले सरणी का उपसर्ग लेंगे जो 2 है और इसे -1 से गुणा करेंगे। तो, नई सरणी {-2, 4, 1, 5, 2} होगी। अब, हम उपसर्ग सरणी बनाएंगे जो {-2, 2, 3, 8, 10} है। अंतिम चरण योग को अधिकतम करना है: -2+2+3+8+10 = 21 जो अंतिम आउटपुट है।
इनपुट: int arr[] = {-1, 4, 2, 1, -9, 6};
आउटपुट: उपसर्ग सरणी है: 1 5 7 8 -1 5 सरणी के उपसर्ग को -1 से गुणा करके सरणी के योग को अधिकतम करें: 19
व्याख्या: हमें एक पूर्णांक सरणी दी गई है। तो हम पहले सरणी का उपसर्ग लेंगे जो -1 है और इसे -1 से गुणा करेंगे। तो, नई सरणी {1, 4, 2, 1, -9, 6} होगी। अब, हम उपसर्ग सरणी बनाएंगे जो {1, 5, 7, 8, -1, 5} है। अंतिम चरण योग को अधिकतम करना है: 1+5+7+8+5 = 19 जो अंतिम आउटपुट है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:
- एक पूर्णांक सरणी घोषित करें और एक अस्थायी वेरिएबल x को -1 पर सेट करें फिर arr[0] को arr[0] * x पर सेट करें।
- सरणी का आकार गणना करें। prefix_arry[size] के रूप में एक उपसर्ग सरणी घोषित करें। फंक्शन create_prefix_arr(arr, size, prefix_array) को उपसर्ग सरणी उत्पन्न करने के लिए कॉल करें। उपसर्ग सरणी प्रिंट करें।
- फंक्शन maximize_sum(prefix_array, size) कॉल करें जो सरणी का अधिकतम योग संग्रहीत करेगा।
- फंक्शन void create_prefix_arr(int arr[], int size, int prefix_array[]) के अंदर:
- prefix_array[0] को arr[0] पर सेट करें।
- i को 0 से सरणी के आकार तक लूप चलाएं। अंदर, prefix_array[i] को prefix_array[i-1] + arr[i] पर सेट करें।
- फंक्शन int maximize_sum(int prefix_array[], int size) के अंदर:
- temp नामक एक अस्थायी वेरिएबल घोषित करें और इसे -1 पर सेट करें।
- i को 0 से सरणी के आकार तक लूप चलाएं। अंदर, temp को max(temp, prefix_array[i]) पर सेट करें।
- arr[temp +1] के रूप में एक सरणी घोषित करें और सरणी के सभी तत्वों को 0 से इनिशियलाइज़ करें।
- i को 0 से सरणी के आकार तक लूप चलाएं। अंदर, arr[prefix_array[i]]++ सेट करें।
- max_sum नामक एक अस्थायी वेरिएबल घोषित करें और इसे 0 पर सेट करें। int i को temp पर घोषित करें।
- WHILE i > 0 लूप शुरू करें। जांचें यदि arr[i] > 0 तो max_sum को max_sum + i पर सेट करें और arr[i-1]-- और arr[i]-- घटाएं। अन्यथा, i को 1 से घटाएं।
- max_sum लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
// उपसर्ग सरणी बनाएं
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
prefix_array[0] = arr[0];
for(int i = 1; i < size; i++) {
prefix_array[i] = prefix_array[i-1] + arr[i];
}
}
// उपसर्ग सरणी का अधिकतम योग ढूंढें
int maximize_sum(int prefix_array[], int size) {
int temp = -1;
for(int i = 0; i < size; i++) {
temp = max(temp, prefix_array[i]);
}
int arr[temp + 1];
memset(arr, 0, sizeof(arr));
for(int i = 0; i < size; i++) {
arr[prefix_array[i]]++;
}
int max_sum = 0;
int i = temp;
while(i > 0) {
if(arr[i] > 0) {
max_sum = max_sum + i;
arr[i-1]--;
arr[i]--;
} else {
i--;
}
}
return max_sum;
}
int main() {
int arr[] = {2, 4, 1, 5, 2};
int x = -1;
arr[0] = arr[0] * x;
int size = sizeof(arr) / sizeof(arr[0]);
int prefix_array[size];
// उपसर्ग सरणी बनाने के लिए फंक्शन कॉल करें
create_prefix_arr(arr, size, prefix_array);
// उपसर्ग सरणी प्रिंट करें
cout << "Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
// उपसर्ग सरणी का अधिकतम योग प्रिंट करें
cout << "\nMaximize the sum of array by multiplying prefix of array with -1 are: " << maximize_sum(prefix_array, size);
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Prefix array is: -2 2 3 8 10 Maximize the sum of array by multiplying prefix of array with -1 are: 21
