Znajdź maksymalną sumę elementów w tablicy (z przekręceniem)

Question

Mając tablicę z liczbami całkowitymi + ve i -ve, znajdź maksymalną sumę, tak aby nie można było pominąć dwóch sąsiednich elementów (tzn. Musisz wybrać co najmniej jeden z nich do przodu).

przykład: -

10, 20, 30, -10, -50, 40, -50, -1, -3

Wydajność: 10 + 20 + + 30-10 40-1 = 89

Answer 1

Użyj nawrót, która uwzględni, że:

dp[i] = max(dp[i - 1] + a[i], <- take two consecutives 
      dp[i - 2] + a[i], <- skip a[i - 1]) 

przypadki bazowe pozostawiamy jako ćwiczenie.

Answer 2

Odpowiedź:


myślę, że ten algorytm pomoże.
1. Utwórz metodę, która daje wynik maksymalnej sumy poszczególnych tablic wejściowych użytkownika, powiedz T [n], gdzie n oznacza sumę nie. elementów.
2. Teraz ta metoda będzie nadal dodawać elementy tablicy, dopóki nie będą pozytywne. Chcemy zmaksymalizować sumę i nie ma sensu opuszczać pozytywnych elementów.
3. Gdy tylko nasza metoda napotka element ujemny, przeniesie wszystkie kolejne negatywne elementy do innej metody, która utworzy nową tablicę, powiedz N [i] tak, że ta tablica będzie zawierała wszystkie kolejne negatywne elementy, które napotkaliśmy w T [n] i zwraca maksymalne wyjście N [i].
W ten sposób nie wpływa to na naszą główną metodę i nadal dodaje pozytywne elementy, a ilekroć napotyka element ujemny, zamiast dodawać swoje rzeczywiste wartości dodaje wynik netto maksymalnej liczby kolejnych ujemnych elementów. Na przykład: T [n] = 29,34,55, -6, -5, -4,6,43, -8, -9, -4, -3,2,78 // tutaj: n = 14

główna metoda działania:

29 + 34 + 55 + (wysyła dane & przyjmie wartość metody wtórnej tablicy [-6, -5, -4]) + 6 + 43 + (wysyła dane & otrzymuje wartość z drugiej metody tablicy [-8, -9, -4, -3]) + 2 + 78
Proces kończy się z maksymalnym wyjściem.

Metoda wtórna robocze:
{

N [i] = dostaje tablicę z metodą głównym lub samo w razie potrzeby. Jest to w zasadzie metoda rekurencyjna.
powiedzieć N [i] zawiera elementy, takie jak N1, N2, N3, N4, itp

dla i> = 3:
Teraz wybór idzie tak.
1. Jeśli weźmiemy N1, możemy powtórzyć tablicę z lewej strony, tj. N [i-1], która ma wszystkie elementy z wyjątkiem N1 w tej samej kolejności.Tak, że wyjście max netto będzie
N1 + (wysyła dane & przyjmie wartość metody wtórnej tablicy N [j -1] rekurencyjnie)
2. Jeżeli nie bierze N1, to nie można pominąć N2. Algorytm Teraz jest jak pierwszy wybór, ale zaczyna się od N2. Więc maksymalna moc w tym przypadku będzie wynosić
N2 + (wysyła dane & pobiera wartość z wtórnej metody tablicy N [i-2] rekursywnie). Tutaj N [i-2] to tablica zawierająca wszystkie elementy N [i] z wyjątkiem N1 & N2 w tej samej kolejności.
Zakończenie: Gdy pozostanie nam tablica o rozmiarze jeden (dla N [i-2]), wówczas musimy wybrać tę konkretną wartość jako brak opcji.
Rekurencje w końcu przyniosą maksymalne wyniki i musimy ostatecznie wybrać wyjście z tego wyboru, które jest więcej. i przekieruj maksymalne wyjście do dowolnego miejsca.

dla i = 2:
musimy wybrać wartość, która jest większa

dla i = 1:
Możemy z pewnością pominąć tę wartość.
Więc max moc w tym przypadku będzie 0.

}

Answer 3

Jeśli widzisz ve całkowitą dodać ją do sumy. Jeśli widzisz ujemną liczbę całkowitą, sprawdź następny zbiór liczb całkowitych, który jest maksymalny, i dodaj go do sumy.

10, 20, 30, -10, -50, 40, -50, -1, -3

dla dodatku 10, 20, 30, max (-10, -50), 40 max (-50, -1) i ponieważ nie ma elementu obok -3 go odrzuć.

Ostatni element przejdzie do sumy, jeśli był + ve.

Answer 4

Myślę, że ta odpowiedź ci pomoże.

danej tablicy:

Given:- 10 20 30 -10 -50 40 -50 -1 -3 

Array1:-10 30 60 50 10 90 40 89 86 

Array2:-10 20 50 40 0 80 30 79 76 

Weź maksymalną wartość array1[n-1],array1[n],array2[n-1],array2[n] i.e 89(array1[n-1])

algorytmu: -

1. dla wartości tablica1 przypisać rray1[0]=a[0],array1=a[0]+a[1] i array2[0]=a[0],array2[1]=a[1].

2. obliczyć wartość array1 od 2 do n jest maksimum sumy array1[i-1]+a[i] lub array1[i-2]+a[i].

   for loop from 2 to n{  
       array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]); 
   
   } 
   

3. podobnie do wartości tablica2 od 2 do n wynosi maksymalnie od sumy array2[i-1]+a[i] lub array2[i-2]+a[i].

   for loop from 2 to n{  
   array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]);  
   } 
   

4. końcu znaleźć maksymalną wartość array1[n-1],array[n],array2[n-1],array2[n];

   int max(int a,int b){  
       return a>b?a:b;  
       } 
   
       int main(){  
       int a[]={10,20,30,-10,-50,40,-50,-1,-3};  
       int i,n,max_sum;  
       n=sizeof(a)/sizeof(a[0]);  
       int array1[n],array2[n];  
       array1[0]=a[0];  
       array1[1]=a[0]+a[1];  
       array2[0]=a[0];  
       array2[1]=a[1];  
   
       for loop from 2 to n{  
       array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]);  
       array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]); 
   
       }  
        --i; 
   
       max_sum=max(array1[i],array1[i-1]);  
       max_sum=max(max_sum,array2[i-1]);  
       max_sum=max(max_sum,array2[i]);  
   
       printf("The max_sum is %d",max_sum);  
        return 0;  
       } 
   

ODP: max_sum jest 89

Answer 5

public static void countSum(int[] a) { 
     int count = 0; 
     int skip = 0; 
     int newCount = 0; 

     if(a.length==1) 
     { 
      count = a[0]; 
     } 
     else 
     { 
      for(int i:a) 
      { 
       newCount = count + i; 
       if(newCount>=skip) 
       { 
        count = newCount; 
        skip = newCount; 
       } 
       else 
       { 
        count = skip; 
        skip = newCount; 
       } 
      } 
     } 
     System.out.println(count); 
    } 
} 

Answer 6

Problem ten można rozwiązać za pomocą podejścia dynamicznego programowania.

Niech arr być dana tablica i opt być tablica do przechowywania optymalnych rozwiązań. opt [i] to maksymalna suma, którą można uzyskać, zaczynając od elementu i, włącznie.

opt[i] = arr[i] + (some other elements after i) 

teraz, aby rozwiązać ten problem mamy iterację tablicy arr tyłu, za każdym razem przechowywania odpowiedź opt [i]. Ponieważ nie można pominąć 2 przylegające do siebie elementy, albo elementu I + 1 lub elementu I + 2 musi być włączone w opt [I].

Więc dla każdego i, opt[i] = arr[i] + max(opt[i+1], opt[i+2])

Zobacz ten kod do zrozumienia:

int arr[n]; // array of given numbers. array size = n. 
nput(arr, n); // input the array elements (given numbers) 

int opt[n+2]; // optimal solutions. 
memset(opt, 0, sizeof(opt)); // Initially set all optimal solutions to 0. 

for(int i = n-1; i >= 0; i--) { 
    opt[i] = arr[i] + max(opt[i+1], opt[i+2]); 
} 

ans = max(opt[0], opt[1]) // final answer. 

Zauważmy, że opt tablica ma n + 2 elementy. Ma to zapobiec uzyskaniu niedozwolonego dostępu do pamięci (pamięć poza zakresem), gdy próbujemy uzyskać dostęp do opt [i + 1] i opt [i + 2] dla ostatniego elementu (n-1).

See the working implementation of the algorithm given above

Answer 7

Niech macierz mieć rozmiar N, dodane jako 1 ... n

Niech f (n) jest funkcją, która stanowi odpowiedź na max suma sub tablicy (1. ..n), tak, że żadne dwa pozostałe elementy nie są kolejne.

f(n) = max (a[n-1] + f(n-2), a(n) + f(n-1)) 

w pierwszej opcji, który - {a [n-1] + f (n-2)}, że opuszcza ostatni element, a ze względu na stan przedstawiono w kwestii wybierania drugiego ostatniego elementu.

W drugiej opcji, którą jest - {a (n) + f (n-1)}, wybieramy ostatni element podbarwy, więc mamy opcję wyboru/odznaczenia drugiego ostatniego elementu.

Zaczynając od przypadku podstawowego:

f(0) = 0 [Subarray (1..0) doesn't exist] 

f(1) = (a[1] > 0 ? a[1] : 0); [Subarray (1..1)] 

f(2) = max(a(2) + 0, a[1] + f(1)) [Choosing atleast one of them] 

Naprzód można obliczyć dowolnego f (n), gdzie n = 1 ... N i przechowywać je obliczyć następujące wyniki. I tak, oczywiście, przypadek f (N) da nam odpowiedź.

Time complexity o(n) 
Space complexity o(n) 

Answer 8

public static int sumz(int a[]) 
{ 
    int total=0; 
    boolean isSkipped=false; 
    for(int i=0;i<a.length;i++) 
    { 
     if(a[i]<0) // we check when value is less than 0 
     { 
      if(i+1<a.length) //to check next element we compare whether next element consist in array or not 
      { 
       if(a[i]>=a[i+1]||isSkipped) // here we check next element less than current element 
       { 
        if(a[i]==a[i+1]) //if its equal to current than we check next to next element to decide this skip 
        { 
         if(i+2<a.length) 
         { 
          if(a[i+2]>a[i+1]) // here we check next to next element if its greater than next than we skip current element 
          { 
           isSkipped=true; 
          }else{ 
           isSkipped=false; // or else we take current element 
           total=total+a[i]; 
          } 
         } 
         else{ 
          total=total+a[i]; 
          isSkipped=false; 
         } 
        } 
        else{ 
         isSkipped=false; // here if its bigger than next we take it and make isSkipped false as we didnt skipped the element 
         total=total+a[i]; 
        } 
       } 
       else if(isSkipped) //if previous element is skipped than we have to take this elements 
       { 
        total=total+a[i]; 
        isSkipped=false; 
       } 
       else // if it failes all condition than we skip element 
       { 
        isSkipped=true; 
       } 
      } 
      else if(isSkipped==false && a[i]>0) //if its last element and last element is not skipped and its greater than 0 than we add it in total 
      { 
       total=total+a[i]; 
       isSkipped=false; 
      } 
     } 
     else 
     { 
      isSkipped=false; // value which are greater than 0 are added directly 
      total=a[i]+total; 
     } 
    } 
    return total; 
}