गैर लगातार तत्वों का अधिकतम योग


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट वीरांगना अमेरिकन एक्सप्रेस Facebook गूगल कब्र ऑक्सिजन वॉलेट ओयो कमरे Paytm Snapchat वॉलमार्ट लैब्स याहू
ऐरे गतिशील प्रोग्रामिंग

समस्या का विवरण

दिए गए “अधिकतम निरंतर तत्वों के अधिकतम योग” में सरणी, आपको गैर-निरंतर तत्वों की अधिकतम राशि खोजने की आवश्यकता है। आप तत्काल पड़ोसी संख्या नहीं जोड़ सकते। उदाहरण के लिए [१,३,५,६,,1,3,5,6,7,8,,,] यहाँ १, ३ आसन्न हैं इसलिए हम उन्हें जोड़ नहीं सकते, और ६, ,1 समीप नहीं हैं इसलिए हम उन्हें जोड़ सकते हैं।

उदाहरण

निवेश

4 10 8 -5 6 9 2

उत्पादन

21

कलन विधि

  1. दो वैरिएबल incl_sum और excl_sum ऐसे लें कि वे उस तत्व को शामिल करके योग बनाते हैं जिस पर आप खड़े हैं और क्रमशः उस तत्व को छोड़कर योग बनता है।
  2. सरणी को पीछे छोड़ें
  3. प्रारंभिक तत्व के रूप में incl_sum को प्रारंभ करें और शून्य होने के लिए excl_sum।
  4. प्रत्येक तत्व के लिए incl_sum और excl_sum का अधिकतम पता लगाएं।
  5. Incl_sum वर्तमान तत्व और excl_sum के योग के बराबर होगा क्योंकि excl_sum की गणना वर्तमान तत्व की तुलना में एक कम सूचकांक तक की गई थी।
  6. excl_sum केवल चरण 4 पर अधिकतम पाया गया होगा।
  7. अंत में, ट्रैवर्सल उत्तर के बाद incl_sum और excl_sum की अधिकतम संख्या होगी।

गैर लगातार तत्वों की अधिकतम राशि खोजने के लिए स्पष्टीकरण

निवेश

6, 12, 10, 26, 20

दिए गए सरणी पर एल्गोरिदम लागू करना,

इंक = 6
एक्स = 0

चरण 1

I = 1 के लिए (वर्तमान तत्व 12 है)
max_till_now = अधिकतम (6,0) = 6
incl = (excl + arrest [i]) = 12
excl = 6

चरण 2

I = 2 के लिए (वर्तमान तत्व 10 है)
max_till_now = अधिकतम (12,6) = 12
incl = (excl + arrest [i]) = 16
excl = 12

चरण 3

I = 3 के लिए (वर्तमान तत्व 26 है)
max_till_now = अधिकतम (16,12) = 16
incl = (excl + arrest [i] = 38)
एक्सेल = 16

चरण 4

I = 4 के लिए (वर्तमान तत्व 20 है)
max_till_now = अधिकतम (38,16) = 38
incl = (excl + arrest [i] = 36)
excl = 38
अंत में उत्तर अधिकतम (38,36) = 38 है।

कार्यान्वयन

C ++ गैर-निरंतर तत्वों का अधिकतम योग खोजने का कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int incl_sum = a[0],excl_sum = 0; //include first element   or exclude it
    int max_sum;
    for(int i=1;i<n;i++)
    {
      max_sum = max(incl_sum,excl_sum);
     incl_sum = excl_sum + a[i]; // excluded sum is till one before the adjacent element  
      excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
    }
    max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum); 
    cout<<max_sum;
     return 0;
}

गैर-निरंतर तत्वों का अधिकतम योग खोजने के लिए जावा कार्यक्रम

import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int incl_sum = arr[0],excl_sum = 0; //include first element   or exclude it
        int max_sum;
        for(int i=1;i<n;i++)
        {
          max_sum = max(incl_sum,excl_sum);
         incl_sum = excl_sum + arr[i]; // excluded sum is till one before the adjacent element  
          excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
        }
        max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum); 
        System.out.println(max_sum);
    }
}
8
1 1 2 2 2 3 4 5 
11

जटिलता विश्लेषण

समय जटिलता - ओ (एन) जहाँ n सरणी का आकार है। यहां हम पूरे ऐरे को ट्रेस करते हैं और इसका उत्तर पाते हैं।
अंतरिक्ष जटिलता - O (1) क्योंकि हम कुछ चर का उपयोग करते हैं जो हमें निरंतर अंतरिक्ष जटिलता की ओर ले जाता है।

संदर्भ