Maximale Summe nicht benachbarter Elemente in 1D-Array

Question

Geben Sie für ein Array von ganzen Zahlen eine maximale Summe nicht benachbarter Elemente an. Zum Beispiel sollten die Eingänge [1, 0, 3, 9, 2, -1] 10 (1 + 9) zurückgeben.

sollte es 3,2 vermeiden, da 9 für 3,2 angrenzt. Maximum in Array + Maximum in Nicht angrenzenden Elementen von 9 (maximales Element in Array).

Da maximale Element ist 9 und nächste maximale, die nicht nebeneinander sein sollte. Daraus ergibt sich 9 + 1 = 10 (da 1 im nicht benachbarten Element des Maximums maximal ist).

Ich versuchte diesen Weg in O (n) + O (Max_Index-1) + O (Array.Length-Max_Index + 2).

Gibt es einen anderen Weg, so dass ich diesen Code in Bezug auf die zeitliche Komplexität optimieren kann.

import java.io.*; 
import java.util.*; 
//Maximum Sum of Non-adjacent Elements 
public class Test{ 
public static void main(String args[]) 
{ 
    int[] a={1, 0, 3, 9, 2,-1,-2,-7}; 
    int max=a[0]; 
    int max_index=0; 
    for(int i=1;i<a.length;++i) 
    { 
     if(max<a[i]) 
     { 
      max=a[i]; 
      max_index=i; 
     } 
    } 
    int m1=a[0]; 
    for(int i=1;i<max_index-1;++i) //get maximum in first half from 0 to max_index-1 
    { 
     if(m1<a[i]) 
      m1=a[i]; 
    } 
    int m2=a[max_index+2]; 
    for(int i=max_index+2;i<a.length;i++)//get maximum in second half max_index+2 to end in array. 
    { 
     if(a[i]>m2) 
     m2=a[i]; 
    } 
    int two_non_adj_max=max+Math.max(m1,m2); 
    System.out.println(two_non_adj_max); 
} 
} 

Answer 1

Sie suchen nach dem Maximalwert M1 in linearer Zeit.

Sie suchen nach dem zweiten nicht benachbarten Maximalwert M2 in Zeilen-Zeit.

S1 = M1 + M2

Wenn M1 das erste oder das letzte Element ist, ist die Antwort S1.

Andernfalls fügen Sie die beiden Werte neben M1:

S2 = A1 + A2

Die Lösung wird dann max (S1, S2)

Ok, ShreePool konkret in S1 interessiert ist.Für andere Leute, die daran interessiert sein könnten, ist das einzig mögliche Paar nicht angrenzender Elemente, die eine größere Summe haben könnten, genau A1 und A2, als wäre eines von ihnen nicht, es wäre nicht benachbart zu M1 und würde es auch tun war ein Kandidat für S1.

Jetzt, um M1 und M2 in linearer Zeit zu finden, gibt es mehrere Optionen. Ich schreibe eine, die nur einen Durchgang erfordert.

Precondition: size >= 3; 
function nonAdjacentMaxPair(a: Integer [], size: Integer): Integer [] is 
    var first: Integer; 
    var second: Integer; 
    var third: Integer; 
    var maxs: Integer [2]; 
    var i: Integer; 
    first := 0; 
    second := 1; 
    third := 2; 
    if (A [1] > A [0]) then 
     first := 1; 
     second := 0; 
    endif; 
    if (A [2] > A [1]) then 
     third := second; 
     second := 2; 
     if (A [2] > A [0]) then 
     second := first; 
     first := 2; 
     endif; 
    endif; 
    i := 3; 
    while (i < size) do 
     if (A [i] > A [third]) then 
     third := i; 
     if (A [i] > A [second]) then 
      third := second; 
      second := i; 
      if(A [i] > A [first]) then 
       second := first; 
       first := i; 
      endif; 
     endif; 
     endif; 
     i := i + 1; 
    endwhile; 
    maxs [0] := first; 
    maxs [1] := second; 
    if (second = first + 1 or second = first - 1) then 
     maxs [1] := third; 
    endif; 
    return maxs; 
endfunction; 

Und S1 ist ein [maxs [0]] + A [maxs [1]]

Hoffnung das ist, was man braucht.

Für den Datensatz: A1 + A2 ist A [maxs [0] - 1] + A [maxs [0] + 1], wenn maxs [0] weder 0 noch die Größe ist.

Answer 2

Soweit ich Ihr Problem verstehen:

int max = Integer.MIN_VALUE; 

for(int i = 0; i < a.length - 2; ++i) { 
    for(int j = i + 2; j < a.length; ++j) { 
     max = Math.max(max, a[i] + a[j]); 
    } 
} 

Dieser Algorithmus hat die Komplexität von O (n ²).

Skizze für einen schnelleren Algorithmus: Sie könnten die Array-Werte mit ihren Indizes in absteigender Reihenfolge sortieren. Dann können Sie nach dem höchsten Paar mit nicht benachbarten Indizes suchen. Dieser Algorithmus benötigt die Schritte (n log n).

Answer 3

Lassen Sie BEST_SUM(i) die maximale Summe der nicht benachbarten Elemente an den Positionen <= i sein.

When i<0, BEST_SUM(i) = 0 
Otherwise: BEST_SUM(i) = max(BEST_SUM(i-1), BEST_SUM(i-2)+a[i]) 

BEST_SUM(a.length-1) ist Ihre Antwort.

HINWEIS: Dies ist die maximale Summe nicht benachbarter Elemente, wie Sie gefragt haben. Mit Blick auf Ihren Code sieht es aus wie Sie kann bedeuten die beste Summe von zwei nicht benachbarte Elemente. Das wäre anders und einfacher.