מאַקסימום סומע פון ​​נאַן קאָנסעקוטיווע עלעמענטן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַקקאָליטע אַמאַזאָן אמעריקאנער עקספּרעסס facebook גוגל ערנסט אָקסיגען וואַללעט OYO רומז Paytm Snapchat וואַלמאַרט לאַבס יאַהאָאָ
מענגע דינאַמיש פּראָגראַממינג

פּראָבלעם סטאַטעמענט  

אין די "מאַקסימום סומע פון ​​נאַן קאָנסעקוטיווע עלעמענטן" געגעבן מענגע, איר דאַרפֿן צו געפֿינען די מאַקסימום סומע פון ​​ניט-קאָנסעקוטיווע עלעמענטן. איר קענט נישט לייגן גלייך חבר נומערן. למשל [1,3,5,6,7,8,] דאָ 1, 3 זענען שכייניש אַזוי מיר קענען נישט לייגן זיי, און 6, 8 זענען נישט שכייניש אַזוי מיר קענען לייגן זיי.

בייַשפּיל  

אַרייַנשרייַב

4 10 8 -5 6 9 2

רעזולטאַט

21

אַלגאָריטהם  

  1. נעמען צוויי וועריאַבאַלז ינקל_סום און עקסקל_סום אַזוי אַז זיי רעפּראַזענץ סומע געגרינדעט דורך ינקלודז די עלעמענט אויף וואָס איר זענט שטייענדיק און סאַכאַקל געגרינדעט דורך עקסקלודינג דעם עלעמענט ריספּעקטיוולי.
  2. אַריבער די מענגע
  3. ערשט איניצולירן incl_sum ווי דער ערשטער עלעמענט און excl_sum צו זיין נול.
  4. געפֿינען די מאַקסימום פון ינקל_סום און עקסקל_סומם פֿאַר יעדער עלעמענט.
  5. Incl_sum וועט זיין גלייַך צו די סומע פון ​​די פאָרשטעלן און excl_sum ווי excl_sum איז קאַלקיאַלייטיד ביז איין ווייניקער אינדעקס ווי די קראַנט עלעמענט.
  6. עקסקל_סום וועט זיין פשוט די מאַקסימום געפֿונען אין שריט 4.
  7. לעסאָף, נאָך טראַווערסאַל ענטפֿערס וועט זיין מאַקסימום פון ינקל_סום און עקסקל_סום.

דערקלערונג צו געפֿינען מאַקסימום סומע פון ​​ניט קאָנסעקוטיווע עלעמענטן  

אַרייַנשרייַב

קסנומקס, קסנומקס, קסנומקס, קסנומקס, קסנומקס

צולייגן אַלגערידאַם אויף די געגעבן מענגע,

ינק = 6
עקסק = 0

שריט קסנומקס

פֿאַר i = 1 (קראַנט עלעמענט איז 12)
max_till_now = max (6,0) = 6
ינקל = (עקסקל + אַרר [איך]) = 12
עקסקל = 6

שריט קסנומקס

זע אויך
געפֿינען די בלויז ריפּעטיטיוו עלעמענט צווישן 1 און N -1

פֿאַר i = 2 (קראַנט עלעמענט איז 10)
max_till_now = max (12,6) = 12
ינקל = (עקסקל + אַרר [איך]) = 16
עקסקל = 12

שריט קסנומקס

פֿאַר i = 3 (קראַנט עלעמענט איז 26)
max_till_now = max (16,12) = 16
ינקל = (עקסקל + אַרר [איך]) = 38
עקסקל = 16

שריט קסנומקס

פֿאַר i = 4 (קראַנט עלעמענט איז 20)
max_till_now = max (38,16) = 38
ינקל = (עקסקל + אַרר [איך]) = 36
עקסקל = 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;
}

Java פּראָגראַם צו געפֿינען מאַקסימום סומע פון ​​ניט קאָנסעקוטיווע עלעמענטן

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 איז די גרייס פון דעם מענגע. דאָ מיר אַריבער די גאנצע מענגע און געפֿינען די ענטפער.
ספעיס קאַמפּלעקסיטי - אָ (1) ווייַל מיר נוצן בלויז עטלעכע וועריאַבאַלז וואָס פירן אונדז צו קעסיידערדיק פּלאַץ קאַמפּלעקסיטי.

זע אויך
דרוקן אַ ביינערי בוים אין ווערטיקאַל סדר

רעפֿערענצן