Максимальная сумма несмежных элементов в одномерном массиве

Учитывая массив целых чисел, найдите максимальную сумму несмежных элементов. Например, входы [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);
}
}
Источник

4 ответа

Решение

Вы ищете максимальное значение M1 в линейном времени.

Вы ищете второе несмежное максимальное значение M2 во времени строки.

S1 = M1 + M2

Если M1 является первым или последним элементом, ответ S1.

В противном случае вы добавляете два значения рядом с M1:

S2 = A1 + A2

Решение тогда max(S1, S2)

Хорошо, ShreePool конкретно интересуется S1. Для других людей, которые могут быть заинтересованы, единственная другая возможная пара несмежных элементов, которая может иметь большую сумму, это точно А1 и А2, как если бы один из них не был, она не была бы смежной с М1, и это был кандидатом на 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, ни размеру.

Источник

Позволять 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) это твой ответ.

ПРИМЕЧАНИЕ. Это максимальная сумма несмежных элементов, как вы и просили. Глядя на ваш код, вы видите, что вы имеете в виду лучшую сумму двух несмежных элементов. Это было бы иначе и проще.

Источник

Насколько я понимаю вашу проблему:

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

Этот алгоритм имеет сложность O(n ²).

Эскиз более быстрого алгоритма: вы можете отсортировать значения массива по его индексам в порядке убывания. Чем вы можете искать самую высокую пару, которая имеет несмежные индексы. Этот алгоритм выполняет O(n log n) шагов.

Источник

пакет абв;

Решение открытого класса {

// int[] A{1,4,5,2,5,4,2}

      public int nonAdjacentMaxSumRepeated(int[] inpArray) {

    int[] a = new int[inpArray.length];
    int k=0;
    for(int i=0,j=0;i<inpArray.length;i++) {
        j=i+1; 
        //System.out.println("i="+i);
        //System.out.println("j="+j);
        System.out.println(inpArray[i]+","+inpArray[j]);
        a[k]=inpArray[i]+inpArray[j];k++;
        i=j;
    }
    
    int x=0;
    for (int i : a) {
     x = Math.max(x, i);
    }
    
    return x;
}

public static void main(String[] args) {
    System.out.println(
    new Solution().nonAdjacentMaxSumRepeated(new int[] {1,3,5,2,6,4,2,7})
    );
}

}

Источник
Другие вопросы по тегам