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

algorithm, arrays, java

Solution

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.

Problem

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.

Original source