arrays - 一维数组中非相邻元素的最大总和

Question

Given an array of integers, find a maximum sum of non-adjacent elements. For example, inputs [1, 0, 3, 9, 2,-1] should return 10 (1 + 9).

应该避免使用 3,2，因为 9 与 3,2 相邻。 maximum in array + maximum in Non adjacent elements of 9(array maximum element in array)

因为最大元素是 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。

你在 linesr 时间内搜索第二个不相邻的最大值 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]]

希望这就是您所需要的。

记录:A1 + A2 是 A [maxs [0] - 1] + A [maxs [0] + 1]，如果 maxs [0] 既不是 0 也不是 size。