Find the largest sum including no more than two consecutive elements from the array

Question

I played around a bit with the algorithms for getting the largest amount without two adjacent elements in the array, but I thought:

If we have an array with n elements and we want to find the largest sum so that 3 elements never touch. To say, if we have an array a = [2, 5, 3, 7, 8, 1], we can choose 2 and 5, but not 2, 5 and 3, because then we have 3 in a row. A large sum with these rules for this array will be equal to: 22 (2 and 5, 7 and 8. 2 + 5 + 7 + 8 = 22)

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

Edit:

I just came to think about what might be useful:

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 that I got in my head, no longer than this.

Answer 1

adi solution can be easily generalized to include up to n adjacent elements. The trick is to maintain an array of n + 1 elements, where the k-th element in the array (0? K? Le) gives the maximum amount, assuming that k previous entries are included in the sum and k + 1- th not:

 /** * 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 the adi solution, it also works in linear time (more precisely, O (mn), where m is the input length and n is the maximum number of adjacent elements allowed in the total) and uses a constant memory size 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 2

An algorithm for the maximum sum such that two elements are not adjacent:
Loop for all elements in arr [] and maintain two sums, including excl, where incl = the maximum amount, including the previous element, and excl = the maximum amount, excluding the previous element.

The maximum amount excluding the current element will be max (including, excluding), and the maximum amount including the current element will be the excl + current element (note that only excl is considered, because the elements cannot be adjacent).

At the end of the cycle, return max on. and not.

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

Difficulty of time: O (n)
Cosmic complexity: O (1)

---

Change 1:
If you understand the code above, we can easily cope with this problem by saving the number of adjacent numbers for the previous position. Here is a working implementation on a given 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; } 

Difficulty of time: O (n)
Cosmic complexity: O (1)

Answer 3

I would suggest that this is an array in a binary tree in that order. This way you can keep track of which item is next to each other. Then just do if (node ​​are not directly connected to each other) to summarize nodes that are not next to each other. You can do this with recursion and return the maximum number, which will simplify the code. Hope it helps.

Answer 4

For a set with elements n there are 2^n ways to split it. Thus, in order to generate all possible sets, just loop from 0:2^n-1 and select the elements from the array with those elements that are set to 1 (carry me, I get 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 array entries. Now the problem is that you do not want to resolve all i values, namely those that contain 3 consecutive 1 . This can be done by checking if the number 7 ( b111 ) is available for 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 */ } } ...