Maksymalna suma elementów nie następujących po sobie

Poziom trudności Średni
Często zadawane pytania Accolita Amazonka American Express Facebook Google Wziąć Portfel Oxigen Pokoje OYO Paytm Snapchat Laboratoria Walmart Yahoo
Szyk Programowanie dynamiczneodwiedzajacy 595

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W podanej „Maksymalnej sumie niekolejnych elementów” szyk, musisz znaleźć maksymalną sumę niekolejnych elementów. Nie możesz dodać numerów bezpośrednich sąsiadów. Na przykład [1,3,5,6,7,8,] tutaj 1, 3 sąsiadują ze sobą, więc nie możemy ich dodać, a 6, 8 nie sąsiadują ze sobą, więc możemy je dodać.

Przykład

Wkład

4 10 8-5 6 9 2

Wydajność

21

Algorytm

  1. Weź dwie zmienne include_sum i excl_sum tak, aby reprezentowały sumę utworzoną przez uwzględnienie elementu, na którym stoisz, i sumę utworzoną przez wykluczenie tego elementu.
  2. Przejdź przez tablicę
  3. Zainicjuj include_sum jako pierwszy element i excl_sum na zero.
  4. Dla każdego elementu znajdź maksimum z inc_sum i excl_sum.
  5. Incl_sum będzie równa sumie obecnego elementu i excl_sum, ponieważ excl_sum została obliczona do jednego indeksu mniej niż bieżący element.
  6. excl_sum będzie po prostu maksimum znalezionym w kroku 4.
  7. Ostatecznie, po przejściu przez trawers, odpowiedź będzie wynosić maksymalnie include_sum i excl_sum.

Wyjaśnienie, jak znaleźć maksymalną sumę niekolejnych elementów

Wkład

6, 12, 10, 26, 20

Stosowanie algorytmu na podanej tablicy,

wz = 6
exc = 0

Krok 1

Dla i = 1 (obecny element to 12)
max_till_now = max (6,0) = 6
w tym = (excl + arr [i]) = 12
excl = 6

Krok 2

Dla i = 2 (obecny element to 10)
max_till_now = max (12,6) = 12
w tym = (excl + arr [i]) = 16
excl = 12

Krok 3

Dla i = 3 (obecny element to 26)
max_till_now = max (16,12) = 16
inclusive = (excl + arr [i]) = 38
wył = 16

Krok 4

Dla i = 4 (obecny element to 20)
max_till_now = max (38,16) = 38
inclusive = (excl + arr [i]) = 36
excl = 38
Ostatecznie odpowiedź to max (38,36) = 38.

Realizacja

C ++ Program do znajdowania maksymalnej sumy niekolejnych elementów

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

Program w języku Java do znajdowania maksymalnej sumy elementów nie następujących po sobie

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

Analiza złożoności

Złożoność czasowa - O (N) gdzie n jest rozmiarem tablicy. Tutaj przechodzimy przez całą tablicę i znajdujemy odpowiedź.
Złożoność przestrzeni - O (1) ponieważ używamy tylko niektórych zmiennych, co prowadzi nas do stałej złożoności przestrzeni.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »