हमें एक पूर्णांक सरणी दी गई है और कार्य पहले किसी सरणी के उपसर्ग को लाना है और फिर इसे -1 से गुणा करना है, दूसरे एक सरणी के उपसर्ग योग की गणना करना और अंत में उत्पन्न उपसर्ग सरणी से अधिकतम योग प्राप्त करना है।
उपसर्ग सरणी −
. के रूप में उत्पन्न होती हैउपसर्ग का पहला तत्वअरे [0] =किसी सरणी का पहला तत्व
उपसर्ग का दूसरा तत्वअरे [1] =उपसर्गअरे [0] + गिरफ्तारी [1]
उपसर्ग का तीसरा तत्वअरे [2] =उपसर्गअरे [1] + गिरफ्तारी [2]
उपसर्ग का चौथा तत्वअरे[3] =उपसर्गअरे[2] + गिरफ्तारी[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+`0 =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+8+5 =19 के रूप में अधिकतम करना है जो कि अंतिम आउटपुट है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है -
-
एक पूर्णांक सरणी और एक अस्थायी चर को x से -1 के रूप में घोषित करें, फिर arr [0] को arr [0] * x पर सेट करें।
-
एक सरणी के आकार की गणना करें। एक उपसर्ग सरणी को prefix_arry [आकार] के रूप में घोषित करें। दिए गए सरणी से उपसर्ग सरणी उत्पन्न करने के लिए create_prefix_arr(arr, size, prefix_array) फ़ंक्शन को कॉल करें। उपसर्ग सरणी प्रिंट करें
-
फ़ंक्शन को कॉल करें max_sum(prefix_array, size) जो सरणी के अधिकतम योग को संग्रहीत करेगा।
-
समारोह के अंदर शून्य create_prefix_arr(int arr[], int size, int prefix_array[])
-
प्रीफ़िक्स_एरे[0] को गिरफ्तारी [0] पर सेट करें।
-
एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें। लूप के अंदर, prefix_array[i] से prefix_array[i-1] + arr[i] सेट करें।
-
-
फ़ंक्शन के अंदर int max_sum(int prefix_array[], int size)
-
अस्थायी चर को अस्थायी घोषित करें और इसे -1 पर सेट करें।
-
एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें। लूप के अंदर, temp को max(temp, prefix_array[i])
. के रूप में सेट करें -
किसी सरणी को arr[temp +1] के रूप में घोषित करें और किसी सरणी के सभी तत्वों को 0 से प्रारंभ करें।
-
एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें। लूप के अंदर, arr[prefix_array[i]]++
. सेट करें -
एक अस्थायी चर को max_sum के रूप में घोषित करें और इसे 0 पर सेट करें। एक चर को int i to temp के रूप में घोषित करें
-
लूप प्रारंभ करें जबकि i>0. IF arr[i]> 0 चेक करें और फिर max_sum को max_sum + i पर सेट करें और arr[i-1]-- को घटाएं और arr[i]-- को घटाएं। ELSE, i को 1 से घटाएं।
-
max_sum लौटाएं।
-
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
prefix_array[0] = arr[0];
for(int i=0; i<size; i++) {
prefix_array[i] = prefix_array[i-1] + arr[i];
}
}
//find the maximum sum of prefix array
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];
//call function to create a prefix array
create_prefix_arr(arr, size, prefix_array);
//print the prefix array
cout<<"Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//print the maximum sum of prefix array
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