一維陣列中非相鄰元素的最大總數

Question

給定一個整數數組，找到非相鄰元素的最大總和。 例如，輸入[1，0，3，9，2，-1]應返回10（1 + 9）。

應該避免3,2，因爲9是相鄰的3,2。最大值在數組中+最大值在9的非相鄰元素中（數組中的最大元素）。

由於最大元素爲9，下一個最大值應該是不相鄰的。導致這個9 + 1 = 10（因爲1是最大的非相鄰元素中的最大值）。

我在O（n）+ O（Max_index-1）+ O（Array.length-Max_index + 2）中試過這種方法。

有沒有其他方法可以根據時間複雜性優化這些代碼。

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

您可以在線性時間內搜索最大值M1。

您可以在liner時間內搜索第二個不相鄰的最大值M2。

S1 = M1 + M2

如果M1是第一或最後一個元素，答案是S1。

否則你上相鄰的兩個值添加到M1：

S2 = A1 + A2

然後將溶液MAX（S1，S2）

好的，ShreePool是在S1中感興趣的具體。對於其他可能感興趣的人來說，唯一可能有較大和的另一對不相鄰元素恰好是A1和A2，好像其中一個不是，它不會與M1相鄰，它會已經是S1的候選人。

現在，要在線性時間內找到M1和M2，有幾種選擇。我寫一個只需要一次傳球的人。

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; 

和S1是A [MAXS [0] + A [MAXS [1]

希望這是你需要的東西。

對於記錄：如果maxs [0]既不是0也不是大小，A1 + A2是A [maxs [0] - 1] + A [maxs [0] + 1]。

Answer 2

據我理解您的問題：

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

該算法的Ø（ñ²）的複雜性。

草圖爲更快的算法：您可以使用索引按降序對數組值進行排序。您可以搜索具有不相鄰索引的最高配對。該算法需要步驟（n log n）步驟。

Answer 3

令BEST_SUM(i)爲位置<= i上的非相鄰元素的最大總和。

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)是你的答案。

注意：這是非相鄰元素的最大總和，就像您要求的那樣。看看你的代碼，它看起來像你可能意味着最好的總和兩個非相鄰元素。這將是不同的，更容易。