Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में m रेंज इंक्रीमेंट ऑपरेशन के बाद सरणी में अधिकतम मान


इस समस्या में, हमें 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 है

  1. - C++ में K नेगेशन के बाद ऐरे योग को अधिकतम करना

    समस्या कथन आकार n का एक ऐरे और एक संख्या k दी गई है। हमें ऐरे को k बार संशोधित करना है। ऐरे संशोधित करने का मतलब है प्रत्येक ऑपरेशन में हम किसी भी ऐरे तत्व arr[i] को उसके नकारात्मक से बदल सकते हैं यानी arr[i] = -arr[i]। कार्य इस ऑपरेशन को इस तरह करना है कि k ऑपरेशन के बाद ऐरे का योग अधिकतम हो। यद

  1. - C++ में सरणी को हटाने के लिए न्यूनतम ऑपरेशन

    विवरणN पूर्णांकों की एक सरणी दी गई है जहां N एक सम संख्या है। सरणी पर दो प्रकार के ऑपरेशन अनुमत हैं।सरणी के किसी भी तत्व का मान 1 से बढ़ाएं।यदि सरणी में दो आसन्न तत्व क्रमागत अभाज्य संख्या हैं, तो दोनों तत्वों को हटाएं।कार्य सरणी के सभी तत्वों को हटाने के लिए आवश्यक न्यूनतम ऑपरेशन की संख्या ज्ञात कर

  1. - C++ प्रोग्राम: सरणी में सबसे छोटे मान की आवृत्ति ज्ञात करना

    यहां हम देखेंगे कि सरणी में सबसे छोटे तत्व की आवृत्ति कैसे ज्ञात करें। मान लें सरणी तत्व [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] हैं, यहां सबसे छोटा तत्व 3 है, और इस तत्व की आवृत्ति 4 है। इसलिए आउटपुट 4 है। इसे हल करने के लिए हम सूची का सबसे छोटा तत्व ज्ञात करेंगे, फिर पहले नंबर की घटनाओं को गिनेंगे