找到最大的总和，包括从一个数组

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. 

这只是我头脑里想到的一个念头，并没有超过这个。

Answer 1

adi's solution可以很容易地推广到允许多达Ñ相邻要包括在总和中的元素。关键是要保持的Ñ + 1个元素，其中，所述阵列（0 ≤ ķ ≤ Ñ）在ķ个元素给出最大总和的阵列假设ķ先前输入是包括在所述总和与ķ + 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））的恒定数量的存储器。事实上，它甚至可以很容易地修改来处理其长度未知的输入流。

Answer 2

我会想象将数组按顺序放入二进制树中。这样你就可以跟踪哪个元素相邻。然后，只需简单地做一个if（节点不是直接相互连接）来求和彼此不相邻的节点。你可以用递归来做到这一点，并返回最大数量，使代码更容易。希望能帮助到你。

Answer 3

算法的最大总和，使得没有两个元件是相邻的：
环路用于ARR []的所有元素和保持两个和含和不含其中含=最大总和包括前一个元素和不包括=最大总和除前一个元素。

排除当前元素的最大总和将为max（包括excl），包括当前元素的max sum将为excl + current元素（请注意，因为元素不能相邻，所以只考虑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）

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 */ } 
    } 
    ...