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

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

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