हमें एक सरणी दी गई है और कार्य उप-सरणी बनाना है ताकि एक वृत्ताकार रूप में उपसरणियों का योग अधिकतम मान प्राप्त करे।
इनपुट - int arr[] ={1, 2, 8, 4, 3, 0, 7}
आउटपुट − अधिकतम सर्कुलर सबअरे योग − 22
. हैस्पष्टीकरण - हमें एक सरणी दी गई है जिसमें {1, 2, 8, 4, 3, 0, 7} है और इसका उप-सरणी अधिकतम योग 7 + 1 + 2+ 8 + 4 22 है।
इनपुट - int arr[] ={ 2, 5, -1, 6, 9, 4, -5}
आउटपुट − अधिकतम सर्कुलर सबअरे योग − 25
. हैस्पष्टीकरण - हमें एक सरणी दी गई है जिसमें {2, 5, -1, 6, 9, 4, -5} है और इसका उप-सरणी अधिकतम योग 4 + 2 + 5 - 1 + 6 + 9 25 है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक तत्वों की एक सरणी इनपुट करें जिसमें सकारात्मक और नकारात्मक दोनों मान हों।
-
एक सरणी के आकार की गणना करें।
-
आगे की प्रक्रिया के लिए फ़ंक्शन में एक सरणी और आकार पास करें।
-
कुल के रूप में एक अस्थायी चर बनाएँ और इसे 0 पर सेट करें
-
एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें
-
लूप के अंदर, टोटल के साथ टोटल सेट करें + arr[i]
-
अस्थायी सेट करें =एआर [0], temp_2 =एआर [0], temp_3 =एआर [0], temp_4 =एआर [0]
-
एक सरणी के आकार तक I से 1 तक के लिए लूप प्रारंभ करें
-
लूप सेट के अंदर अस्थायी =अधिकतम (अस्थायी + गिरफ्तारी [i], गिरफ्तारी [i]), temp_2 =अधिकतम (temp_2, अस्थायी), temp_3 =मिनट (temp_3 + गिरफ्तारी [i], गिरफ्तारी [i]), temp_4 =मिनट (temp_4, temp_3)
-
IF size ==1 चेक करें और फिर arr[0]
लौटाएं -
IF temp_4 ==कुल जांचें, फिर temp_2 वापस करें
-
max_sum =max(temp_3, कुल - temp_4) सेट करें
-
वापसी max_sum
-
परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
int total = 0;
for (int i = 0; i < size; i++){
total += arr[i];
}
int temp = arr[0];
int temp_2 = arr[0];
int temp_3 = arr[0];
int temp_4 = arr[0];
for (int i = 1; i < size; i++){
temp = max(temp + arr[i], arr[i]);
temp_2 = max(temp_2, temp);
temp_3 = min(temp_3 + arr[i], arr[i]);
temp_4 = min(temp_4, temp_3);
}
if (size == 1){
return arr[0];
}
if (temp_4 == total){
return temp_2;
}
int max_sum = max(temp_3, total - temp_4);
return max_sum;
}
int main(){
int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Maximum circular subarray sum is: 25