हमें एक सरणी दी गई है और कार्य उपसरणी बनाना है जैसे कि परिपत्र तरीके से उपसरणी का योग अधिकतम मान देगा।
इनपुट - 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 होगी।
उपयोग किया गया दृष्टिकोण
- सकारात्मक और नकारात्मक मानों वाले पूर्णांक तत्वों की एक सरणी इनपुट करें।
- सरणी का आकार गणना करें।
- आगे की प्रक्रिया के लिए सरणी और आकार को फ़ंक्शन में पास करें।
- एक अस्थायी चर
totalबनाएं और इसे 0 पर सेट करें - i से 0 से सरणी के आकार तक लूप FOR शुरू करें
- लूप के अंदर, total को total + arr[i] के साथ सेट करें
temp = arr[0], temp_2 = arr[0], temp_3 = arr[0], temp_4 = arr[0]सेट करें- i से 1 से सरणी के आकार तक लूप FOR शुरू करें
- लूप के अंदर सेट करें:
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 तो arr[0] लौटाएं
- जांचें IF temp_4 == total तो temp_2 लौटाएं
max_sum = max(temp_3, total - temp_4)सेट करें- max_sum लौटाएं
- परिणाम प्रिंट करें।
C++ कार्यान्वयन
#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
