इस समस्या में, हमें N तत्वों की एक सरणी arr[] दी गई है जिसे 0 से प्रारंभिकृत किया गया है। हमारा कार्य C++ में m रेंज इंक्रीमेंट ऑपरेशन के बाद सरणी में अधिकतम मान ढूंढने के लिए एक प्रोग्राम बनाना है।
समस्या विवरण
सरणी पर, हम m रेंज इंक्रीमेंट ऑपरेशन निम्न प्रकार के करेंगे,
update[L, R, K] = रेंज में सभी तत्वों में मान K जोड़ें।
सरणी पर m ऑपरेशन करने के बाद। हमें सरणी में अधिकतम मान वाले तत्व को ढूंढना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
N = 6, m = 4 Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}
आउटपुट
34
व्याख्या
arr[] = {0, 0, 0, 0, 0, 0} Update 1 {1, 4, 12} : arr[] = {0, 12, 12, 12, 12, 0} Update 2 {0, 3, 5} : arr[] = {5, 17, 17, 17, 12, 0} Update 3 {1, 5, 7} : arr[] = {5, 24, 24, 24, 19, 7} Update 4 {3, 5, 10} : arr[] = {5, 24, 24, 34, 29, 17}
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल तरीका सरणी के मानों को बस अपडेट करना है और फिर सभी ऑपरेशन हो जाने के बाद। सरणी का अधिकतम तत्व ढूंढना।
उदाहरण
हमारे समाधान के काम को दिखाने वाला प्रोग्राम,
#include<iostream> using namespace std; int findmax(int arr[], int N){ int maxVal = 0; for(int i = 0; i < N; i++){ if(maxVal < arr[i]){ maxVal = arr[i]; } } return maxVal; } void updateVal(int arr[], int L, int R, int K){ for(int i = L; i <= R; i++ ){ arr[i] += K; } } int main(){ int N = 5; int arr[N] = {0}; int M = 4; int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}; for(int i = 0; i < M; i++){ updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]); } cout<<"सरणी में अधिकतम मान "<<M<<" रेंज इंक्रीमेंट ऑपरेशन के बाद है "<<findmax(arr, N); return 0; }
आउटपुट
4 रेंज इंक्रीमेंट ऑपरेशन के बाद सरणी में अधिकतम मान 34 है
यह ऑपरेशन अच्छा है लेकिन प्रत्येक क्वेरी के लिए रेंज पर पुनरावृति करता है जिससे जटिलता O(m*N) क्रम की हो जाती है।
एक बेहतर दृष्टिकोण प्रत्येक रेंज इंक्रीमेंट ऑपरेशन के लिए L में K जोड़ना और R+1 से K घटाना है। और फिर सबसे बड़ा मैक्सिमा मान ढूंढना यानी सरणी में प्रत्येक मान के लिए योग मान अपडेट करना और ऑपरेशन में घटित अधिकतम मान ढूंढना।
उदाहरण
हमारे समाधान के काम को दिखाने वाला प्रोग्राम,
#include<iostream> using namespace std; int FindMaximum(int a, int b){ if(a > b) return a; return b; } int findmax(int arr[], int N){ int maxVal = 0; int sum = 0; for(int i = 0; i < N; i++){ sum += arr[i]; maxVal = FindMaximum(maxVal, sum); } return maxVal; } void updateVal(int arr[], int L, int R, int K){ arr[L] += K; arr[R+1] -= K; } int main(){ int N = 5; int arr[N] = {0}; int M = 4; int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}; for(int i = 0; i < M; i++){ updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]); } cout<<"सरणी में अधिकतम मान "<<M<<" रेंज इंक्रीमेंट ऑपरेशन के बाद है "<<findmax(arr, N); return 0; }
आउटपुट
4 रेंज इंक्रीमेंट ऑपरेशन के बाद सरणी में अधिकतम मान 34 है