从一个数组中找出至多包含两个连续元素的最大和

Question

我一直在尝试算法，用于获取数组中不相邻元素的最大和，但我想：

如果我们有一个n个元素的数组，并且我们想要找到最大的总和，以便3个元素永远不会接触。也就是说，如果我们有数组a = [2, 5, 3, 7, 8, 1]，我们可以选择2和5，但不能选择2、5和3，因为此时有3个相邻。按照这些规则，该数组的最大总和为：22（2和5、7和8，2 + 5 + 7 + 8 = 22）

我不确定如何实现它，有什么想法吗？

编辑：

我只想到了可能要做的事情：

让我们坚持使用同样的数组：

int[] a = {2, 5, 3, 7, 8, 1};
int{} b = new int[n}; //an array to store results in
int n = a.length;
// base case
b[1] = a[1];
// go through each element:
for(int i = 1; i < n; i++)
{
    /* find each possible way of going to the next element
    use Math.max to take the "better" option to store in the array b*/
}
return b[n]; // return the last (biggest) element.

这只是我脑海中的一个想法，还没有超过这个长度。

- Mappan

---

展示你所尝试过的。 - Philipp Sander

我还没有写任何代码，只是在思考这个问题。基本情况当然是第一个元素，对于其余的元素，我认为最好将已有的结果存储在一个数组中。然后我可以将数组中的内容与Math.max(possibility1+Array[latest-element], possibility2+Array[latest-2-element])进行比较，因为在到达下一个元素之前，你无法知道下一个元素是什么。将其放在一个for循环中来遍历数字数组。但是，这只是我的思考“进展”到了这里。 - Mappan

Answer 1

最大子序列和问题:
遍历arr[]中的所有元素，并维护两个和incl和excl，其中incl = 包括前一个元素在内的最大和，excl = 不包括前一个元素在内的最大和。

不包括当前元素的最大和将是max(incl, excl)，而包括当前元素的最大和将是excl + current element（注意只考虑excl，因为元素不能相邻）。

循环结束时返回incl和excl的最大值。

实现：

#include<stdio.h>

/*Function to return max sum such that no two elements
 are adjacent */
int FindMaxSum(int arr[], int n)
{
  int incl = arr[0];
  int excl = 0;
  int excl_new;
  int i;

  for (i = 1; i < n; i++)
  {
     /* current max excluding i */
     excl_new = (incl > excl)? incl: excl;

     /* current max including i */
     incl = excl + arr[i];
     excl = excl_new;
  }

   /* return max of incl and excl */
   return ((incl > excl)? incl : excl);
}

/* Driver program to test above function */
int main()
{
  int arr[] = {5, 5, 10, 100, 10, 5};
  printf("%d \n", FindMaxSum(arr, 6));
  getchar();
  return 0;
}

时间复杂度：O(n)
空间复杂度：O(1)

---

编辑 1：
如果你理解以上代码，我们可以通过维护前一个位置的已相邻数字的计数来轻松解决此问题。 以下是所需问题的工作实现

//We could assume we store optimal result upto i in array sum
//but we need only sum[i-3] to sum[i-1] to calculate sum[i]
//so in this code, I have instead maintained 3 ints
//So that space complexity to O(1) remains

#include<stdio.h>

int max(int a,int b)
{
    if(a>b)
        return 1;
    else
        return 0;
}

/*Function to return max sum such that no three elements
 are adjacent */
int FindMaxSum(int arr[], int n)
{
  int a1 = arr[0]+arr[1];//equivalent to sum[i-1]
  int a2 =arr[0];//equivalent to sum[i-2]
  int a3 = 0;//equivalent to sum [i-3]
  int count=2;
  int crr = 0;//current maximum, equivalent to sum[i]
  int i;
  int temp;

  for (i = 2; i < n; i++)
  {
      if(count==2)//two elements were consecutive for sum[i-1]
      {
          temp=max(a2+arr[i],a1);
          if(temp==1)
          {
              crr= a2+arr[i];
              count = 1;
          }
          else
          {
              crr=a1;
              count = 0;
          }
          //below is the case if we sould have rejected arr[i-2]
          // to include arr[i-1],arr[i]
          if(crr<(a3+arr[i-1]+arr[i]))
          {
              count=2;
              crr=a3+arr[i-1]+arr[i];
          }
      }
      else//case when we have count<2, obviously add the number
      {
          crr=a1+arr[i];
          count++;
      }
      a3=a2;
      a2=a1;
      a1=crr;
  }
  return crr;
}

/* Driver program to test above function */
int main()
{
  int arr[] = {2, 5, 3, 7, 8, 1};
  printf("%d \n", FindMaxSum(arr, 6));
  return 0;
}

时间复杂度：O(n) 空间复杂度：O(1)

- Aditya

---

这是用于确定没有两个相邻元素的最大数字的代码，我在思考如果两个元素可以相邻，但从不超过三个连续的最佳方法是什么。 :) - Mappan

没问题，这可以轻松地推广到允许相邻元素数量的任何数字，可以看看我下面的回答。（附：对于灵感给adi点赞。） - Ilmari Karonen

这并没有回答问题。它回答了“最大和，使得没有两个元素相邻”的问题。然而，这篇文章中提出的问题是“从数组中找到包括最多两个连续元素的最大总和”。这个答案不允许添加相邻的元素，但是这篇文章中的问题允许最多添加2个相邻的元素。为什么有这么多人点赞呢？ - But I'm Not A Wrapper Class

请查看添加的代码，主要技巧保持不变。只是案例数量增加了。已测试 {1, 4, 3, 2, 6, 5} 和 {2, 5, 3, 7, 8, 1}。 - Aditya

@adi 好的更新。虽然我无法测试它，但希望其他人可以确认一下。 - But I'm Not A Wrapper Class

Answer 2

adi 的解决方案 可以轻松地推广到允许将最多 n 个相邻元素包含在总和中。窍门在于维护一个包含 n +1 个元素的数组，其中数组的第 k 个元素（0 ≤ k ≤ n）给出了假设前 k 个输入被包含在总和中，第 k+1 个输入不被包含在总和中的最大和：

/**
 * Find maximum sum of elements in the input array, with at most n adjacent
 * elements included in the sum.
 */
public static int maxSum (int input[], int n) {
    int sums[] = new int[n+1];  // new int[] fills the array with zeros
    int max = 0;

    for (int x: input) {
        int newMax = max;
        // update sums[k] for k > 0 by adding x to the old sums[k-1]
        // (loop from top down to avoid overwriting sums[k-1] too soon)
        for (int k = n; k > 0; k--) {
            sums[k] = sums[k-1] + x;
            if (sums[k] > newMax) newMax = sums[k];
        }
        sums[0] = max;  // update sums[0] to best sum possible if x is excluded
        max = newMax;   // update maximum sum possible so far
    }
    return max;
}

和adi的解决方案一样，这个解决方案也在线性时间内运行（确切地说是O(mn)，其中m是输入长度，n是允许相邻元素之和的最大数量），并且使用常量内存量，与输入长度无关（O(n)）。实际上，它甚至可以轻松修改以处理长度未知的输入流。

- Ilmari Karonen

---

如果我输入数组 [1, 4, 3, 2, 6, 5]，得到的答案是21，但正确答案应该是18：_ 4 3 _ 6 5。但是如果你把所有元素加在一起，你会得到21。如果我加上我例子中的数组([2, 5, 3, 7, 8, 1])，我得到的是26而不是22，如果你把所有元素加在一起，你会得到26。 - Mappan

@Zanii：奇怪。这对我有效。 你是否传递了正确的 n 值（即你的情况下为2）？ - Ilmari Karonen

是的，那就是问题所在，我只是没有仔细阅读评论。 - Mappan

Answer 3

我会考虑按照这个顺序将数组放入二叉树中。这样你就可以跟踪哪个元素是彼此相邻的。然后只需简单地使用 if (节点没有直接相互链接) 来计算不相邻的节点之和。你可以用递归来做，并返回最大值，这样编码会更容易。希望有所帮助。

- Ivan Chan

Answer 4

对于一个包含 n 个元素的集合，有 2^n 种划分方式。因此，要生成所有可能的集合，只需从 0:2^n-1 循环，并选择数组中那些设置为 1 的元素（请耐心等待，我将回答您的问题）：

max = 0;
for (i = 0; i < 1<<n; ++i) {
  sum = 0;
  for (j = 0; j < n; ++j) {
    if (i & (1<<j)) { sum += array[j]; }
  }
  if (sum > max) { /* store max and store i */ }
}

这将找到数组条目的最大求和方式。现在，您想要的问题是不允许所有值的i - 特别是那些包含3个连续的1的值。可以通过测试数字7（b111）是否在任何位移中可用来实现此目的：

for (i = 0; i < 1<<n; ++i) {
  for (j = 0; j < n-2; ++j) {
    if ((i & (7 << j)) == (7 << j)) { /* skip this i */ }
  }
  ...

- JoshG79