Бірізді емес элементтердің максималды қосындысы  


Күрделілік дәрежесі орта
Жиі кіреді Акколит Amazon American Express Facebook Google Ұстаңыз Оксиген әмиян OYO бөлмелері Paytm Snapchat Walmart зертханалары Yahoo
Array Динамикалық бағдарламалау

Проблемалық мәлімдеме  

«Бірізді емес элементтердің максималды қосындысында» келтірілген массив, бірізді емес элементтердің максималды қосындысын табу керек. Сіз жақын маңдағы нөмірлерді қоса алмайсыз. Мысалы, [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. Әрбір элемент үшін 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
exc = 0

қадам 1

I = 1 үшін (ағымдағы элемент 12)
max_till_now = max (6,0) = 6
incl = (excl + arr [i]) = 12
қоспағанда = 6

қадам 2

Сондай-ақ, қараңыз
1-ден N-1 аралығындағы қайталанатын жалғыз элементті табыңыз

I = 2 үшін (ағымдағы элемент 10)
max_till_now = max (12,6) = 12
incl = (excl + arr [i]) = 16
қоспағанда = 12

қадам 3

I = 3 үшін (ағымдағы элемент 26)
max_till_now = max (16,12) = 16
incl = (excl + arr [i]) = 38
қоспағанда = 16

қадам 4

I = 4 үшін (ағымдағы элемент 20)
max_till_now = max (38,16) = 38
incl = (excl + arr [i]) = 36
қоспағанда = 38
Соңында жауап max (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

Күрделілікті талдау  

Уақыттың күрделілігі - O (N) Мұндағы n - массивтің өлшемі. Мұнда біз бүкіл массивті айналып өтіп, жауабын табамыз.
Ғарыштық күрделілік - O (1) өйткені біз кейбір айнымалыларды қолданамыз, бұл бізді үнемі кеңістіктің күрделілігіне әкеледі.

Сондай-ақ, қараңыз
Екілік ағашты тігінен басып шығарыңыз

Әдебиеттер тізімі