Ardıcıl Olmayan Elementlərin Maksimum Cəmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon American Express Facebook google Ağır Oxigen cüzdanı OYO Otaqları Paytm Snapchat Walmart Laboratoriyaları Yahoo
Geyim Dinamik proqramlaşdırmaBaxılıb 537

Problem bəyanat

Verilən “Ardıcıl Olmayan Elementlərin Maksimum Cəmi” ndə array, ardıcıl olmayan elementlərin maksimum cəmini tapmaq lazımdır. Dərhal qonşu nömrələrini əlavə edə bilməzsiniz. Məsələn [1,3,5,6,7,8,] burada 1, 3 bitişikdir, ona görə əlavə edə bilmirik, 6, 8 isə bitişik deyil, əlavə edə bilərik.

misal

Input

4 10 8 -5 6 9 2

Buraxılış

21

Alqoritm

  1. Üzərində olduğunuz element daxil olmaqla əmələ gələn cəmi və müvafiq olaraq həmin element xaric edilərək cəmini təmsil edəcək şəkildə iki dəyişən alın və excl_sum.
  2. Dizini keçin
  3. İlk element kimi incl_sum başlayın və sıfır olan excl_sum.
  4. Hər bir element üçün incl_sum və excl_sum maksimumunu tapın.
  5. Incl_sum indiki elementin cəminə bərabər olacaq və excl_sum cari elementdən bir daha az göstəriciyə qədər hesablanmışdır.
  6. excl_sum sadəcə 4-cü addımda tapılan maksimum olacaqdır.
  7. Nəhayət, keçiddən sonra cavab maksimum incl_sum və excl_sum olacaqdır.

Ardıcıl Olmayan Elementlərin Maksimum Cəmini tapmaq üçün izah

Input

6, 12, 10, 26, 20

Verilmiş massivdə alqoritm tətbiq etmək,

daxil = 6
istisna = 0

Step 1

I = 1 üçün (cari element 12-dir)
max_till_now = max (6,0) = 6
incl = (istisna + arr [i]) = 12
xaric = 6

Step 2

I = 2 üçün (cari element 10-dir)
max_till_now = max (12,6) = 12
incl = (hariç + arr [i]) = 16
xaric = 12

Step 3

I = 3 üçün (cari element 26-dir)
max_till_now = max (16,12) = 16
incl = (hariç + arr [i]) = 38
xaric = 16

Step 4

I = 4 üçün (cari element 20-dir)
max_till_now = max (38,16) = 38
incl = (hariç + arr [i]) = 36
xaric = 38
Nəhayət cavab max (38,36) = 38-dir.

Həyata keçirilməsi

Ardıcıl Olmayan Elementlərin Maksimum Cəmini tapmaq üçün C ++ Proqramı

#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;
}

Ardıcıl Olmayan Elementlərin Maksimum Cəmini tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi - O (N) burada n massivin ölçüsüdür. Burada bütün massivi gəzirik və cavabını tapırıq.
Kosmik Mürəkkəblik - O (1) çünki bəzi dəyişənlərdən yalnız bizi daimi kosmik mürəkkəbliyə aparan istifadə edirik.

References

Translate »