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

C++ में अधिकतम योग घटता हुआ सबसीक्वेंस


इस समस्या में, हमें N पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य C++ में अधिकतम योग घटता हुआ सबसीक्वेंस ढूंढना है।

समस्या विवरण

हम सरणी से तत्वों का अधिकतम योग ढूंढेंगे जैसे कि सबसीक्वेंस सख्ती से घटता हुआ हो।

आइए एक उदाहरण से समस्या को समझते हैं,

इनपुट

arr[] = {3, 1, 6, 10, 5, 2, 9}

आउटपुट

17

व्याख्या

अधिकतम योग वाला घटता हुआ सबसीक्वेंस {10, 5, 2} = 10 + 5 + 2 = 17 है।

समाधान दृष्टिकोण

यहां, हम समाधान खोजने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। यहां, हम एक maxSum[] सरणी बनाएंगे जो इंडेक्स i तक अधिकतम योग संग्रहीत करेगी। सरणी मानों को खोजने के लिए निम्न सूत्र का उपयोग किया जाता है:

maxSum[i] = arr[i] + max(maxSum[0 ... (i-1)])

अधिकतम योग maxSum[] सरणी के अधिकतम तत्व द्वारा दिया जाता है।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <iostream> 
using namespace std; 
int findMaxSumDecSubSeq(int arr[], int N){ 
    int maximumSum = 0; 
    int maxSum[N]; 
    for (int i = 0; i < N; i++) 
        maxSum[i] = arr[i]; 
    for (int i = 1; i < N; i++) 
        for (int j = 0; j < i; j++) 
            if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i]) 
                maxSum[i] = maxSum[j] + arr[i]; 
    for (int i = 0; i < N; i++) 
        if (maximumSum < maxSum[i]) 
            maximumSum = maxSum[i]; 
    return maximumSum; 
} 
int main(){ 
    int arr[] = { 5, 4, 100, 3, 2, 101, 1 }; 
    int N= sizeof(arr) / sizeof(arr[0]); 
    cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N); 
    return 0; 
}

आउटपुट

The maximum sum of decreasing subsequence is 106
  1. - C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo m)

    इस समस्या में, हमें आकार n की एक सरणी और एक पूर्णांक m दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम उपसरणी योग मॉड्यूलो m ढूंढे। प्रोग्राम विवरण - यहां, हम उपसरणी के सभी तत्वों के योग को m से विभाजित करके प्राप्त अधिकतम मान ढूंढेंगे। आइए एक उदाहरण से समझते हैं: इनपुट - सरणी = {4

  1. - C++ में प्रीफिक्स सम का उपयोग करके O(n) में अधिकतम सबएरे सम

    समस्या कथनसकारात्मक और नकारात्मक पूर्णांकों का एक सरणी दिया गया है, उस सरणी में अधिकतम सबएरे सम ज्ञात करें।उदाहरणयदि इनपुट सरणी है {-12, -5, 4, -1, -7, 1, 8, -3} तो आउटपुट 9 होगा।एल्गोरिदमइनपुट सरणी का प्रीफिक्स सम निकालें।प्रारंभ करें: min_prefix_sum = 0, res = -infinitei = 0 से n तक लूप बनाए रखें

  1. - C++ में ऐरे में अधिकतम संतुलन योग

    समस्या कथन एक ऐरे arr[] दिया गया है। इंडेक्स i के लिए arr[] में अधिकतम प्रीफिक्स योग का मान ढूंढें जो सफिक्स योग भी हो। उदाहरण यदि इनपुट ऐरे है - Arr[] = {1, 2, 3, 5, 3, 2, 1} तो आउटपुट 11 है - प्रीफिक्स योग = arr[0..3] = 1 + 2 + 3 + 5 = 11 और सफिक्स योग = arr[3..6] = 5 + 3 + 2 + 1 = 11 एल्गोरिदम