4

我一直在玩一些算法来获得最大的和，而数组中没有两个相邻的元素，但我在想：

如果我们有一个包含 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.

这只是我脑海中的一个想法，还没有达到比这更长的时间。

4

4 回答 4

6

最大和的算法，使得没有两个元素相邻：
循环 arr[] 中的所有元素并保持两个和 incl 和 excl 其中 incl = 包括前一个元素的最大和，excl = 不包括前一个元素的最大和。

不包括当前元素的最大和将是 max(incl, excl) 并且包括当前元素的最大和将是 excl + 当前元素（注意，只考虑 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)

于 2013-08-27T13:44:57.917 回答
5

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 ))。事实上，它甚至可以很容易地修改为处理预先不知道长度的输入流。

于 2013-08-27T14:49:03.917 回答
1

我会想象按该顺序将数组放入二叉树中。这样您就可以跟踪哪个元素彼此相邻。然后只需简单地做一个 if（节点不直接相互链接）来对不相邻的节点求和。您可以通过递归来实现并返回最大数量，从而使事情更容易编码。希望能帮助到你。

于 2013-08-27T13:43:09.320 回答
0

对于具有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's 的值。这可以通过测试数字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 */ }
  }
  ...
于 2013-08-27T14:53:37.487 回答