一维数组中不相邻元素的最大和 [英] Maximum Sum of Non-adjacent Elements in 1D array

问题描述

给定一个整数数组，找到不相邻元素的最大和. 例如，输入[1、0、3、9、2，-1]应返回10(1 + 9).

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相邻.数组中的最大值+ 9个非相邻元素中的最大值(数组中的最大元素).

there should be avoid 3,2 since 9 is adjacent for 3,2. maximum in array + maximum in Non adjacent elements of 9(maximum element in array).

因为最大元素是9，下一个最大值应该不相邻.结果是9 + 1 = 10(因为在最大的非相邻元素中最大为1).

Since maximum element is 9 and next maximum which should be non-adjacent. resulting this 9+1=10(since 1 is maximum in non adjacent element of maximum).

我在O(n)+ O(Max_index-1)+ O(Array.length-Max_index + 2)中尝试过这种方式.

I tried this way in 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);
}
}

推荐答案

您将在线性时间内搜索最大值M1.

You search for the maximum value M1 in linear time.

您可以搜索以秒为单位的第二个非相邻最大值M2.

You search for the second non-adjacent maximum value M2 in linesr time.

S1 = M1 + M2

S1 = M1 + M2

如果M1是第一个或最后一个元素，则答案为S1.

If M1 is the first or the last element, the answer is S1.

否则，您将M1附近的两个值相加:

Otherwise you add the two values adjacent to M1:

S2 = A1 + A2

S2 = A1 + A2

然后解为max(S1，S2)

The solution is then max(S1, S2)

好的，ShreePool对S1特别感兴趣.对于其他可能感兴趣的人，可能具有更大总和的唯一其他可能的一对非相邻元素恰好是A1和A2，就好像其中一个不是，它不会与M1相邻，并且它会与M1相邻.已经成为S1的候选人.

Ok, ShreePool is interested concretely in S1. For other people who might be interested, the only other possible pair of non-adjacent elements which could have a bigger sum are precisely A1 and A2, as if one of them wasn't, it wouldn't be adjacent to M1 and it would have been a candidate for S1.

现在，要在线性时间内找到M1和M2，有几种选择.我写的只需要一遍.

Now, to find M1 and M2 in linear time, there are several options. I write one which requires only one pass.

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 [最大[0]] + A [最大[1]]

And S1 is A [maxs [0]] + A [maxs [1]]

希望这就是您所需要的.

Hope this is what you needed.

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

For the record: A1 + A2 is A [maxs [0] - 1] + A [maxs [0] + 1], if maxs [0] is neither 0 nor size.

这篇关于一维数组中不相邻元素的最大和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！