Find the largest sum including at most two consecutive elements from an array

Question

I've been playing around a bit with the algorithms for getting the largest sum with no two adjacent elements in an array but I was thinking:

If we have an array with n elements and we want to find the largest sum so that 3 elements never touch. That's to say if we have the array a = [2, 5, 3, 7, 8, 1] we can pick 2 and 5 but not 2, 5 and 3 because then we have 3 in a row. The larget sum with these rules for this array would be: 22 (2 and 5, 7 and 8. 2+5+7+8=22)

I'm not sure how I would implement this, any ideas?

Edit:

I've only come so far as to think about what might be good to do:

Let's just stick to the same array:

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.

This is just a thought I got in my head, hasn't reached longer than this.

Answer 1

Algorithm for Maximum sum such that no two elements are adjacent:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

Implementation:

#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;
}

Time Complexity: O(n)
Space Complexity: O(1)

---

Edit 1:
If you understand the above code, we can easily do this problem by maintaining the count of already adjacent numbers for previous position. Here is a working implementation to the required question

//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;
}

Time Complexity: O(n)
Space Complexity: O(1)

Answer 2

adi's solution can be easily generalized to allow up to n adjacent elements to be included in the sum. The trick is to maintain an array of n + 1 elements, where the k-th element in the array (0 ≤ k ≤ n) gives the maximum sum assuming that the k previous inputs are included in the sum and the k+1-th isn't:

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

Like adi's solution, this one also runs in linear time (to be exact, O(mn), where m is the length of the input and n is the maximum number of adjacent elements allowed in the sum) and uses a constant amount of memory independent of the input length (O(n)). In fact, it could even be easily modified to process input streams whose length is not known in advance.

Answer 3

For a set with n entries, there are 2^n ways to partition it. So to generate all possible sets, just loop from 0:2^n-1 and pick the elements from the array with those entries set to 1 (bear with me; I'm getting to your question):

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

This will find the maximum way to sum the entries of an array. Now, the issue you want is that you don't want to allow all values of i - specifically those that contain 3 consecutive 1's. This can be done by testing if the number 7 (b111) is available at any bit-shift:

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

Answer 4

I would imagine putting the array into a binary tree in that order. That way you can keep track of which element is next to each other. Then just simply do an if (node is not directly linked to each other) to sum the nodes which are not next to each other. You can potentially do it with recursion and return the maximum number, makes things easier to code. Hope it helps.