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

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

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