Maximum subsequence sum such that no three are consecutive

http://www.geeksforgeeks.org/maximum-subsequence-sum-such-that-no-three-are-consecutive/

Given a sequence of positive numbers, find the maximum sum that can be formed which has no three consecutive elements present.

Input: arr[] = {3000, 2000, 1000, 3, 10}
Output: 5013 
3000 + 2000 + 3 + 10 = 5013

We maintain an auxiliary array sum[] (of same size as input array) to find the result.

sum[i] : Stores result for subarray arr[0..i], i.e.,
         maximum possible sum in subarray arr[0..i]
         such that no three elements are consecutive.

sum[0] = arr[0]

// Note : All elements are positive
sum[1] = arr[0] + arr[1]

// We have three cases
// 1) Exclude arr[2], i.e., sum[2] = sum[1]
// 2) Exclude arr[1], i.e., sum[2] = sum[0] + arr[2]
// 3) Exclude arr[0], i.e., sum[2] = arr[1] + arr[2] 
sum[2] = max(sum[1], arr[0] + arr[2], arr[1] + arr[2])

In general,
// We have three cases
// 1) Exclude arr[i],  i.e.,  sum[i] = sum[i-1]
// 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
// 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1] 
sum[i] = max(sum[i-1], sum[i-2] + arr[i],
             sum[i-3] + arr[i] + arr[i-1])

int maxSumWO3Consec(int arr[], int n)

{

    // Stores result for subarray arr[0..i], i.e.,

    // maximum possible sum in subarray arr[0..i]

    // such that no three elements are consecutive.

    int sum[n];

    // Base cases (process first three elements)

    sum[0] = arr[0];

    sum[1] = arr[0] + arr[1];

    sum[2] = max(sum[1], arr[1] + arr[2]);

    // Process rest of the elements

    // We have three cases

    // 1) Exclude arr[i],  i.e.,  sum[i] = sum[i-1]

    // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]

    // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]

    for (int i=3; i<n; i++)

        sum[i] = max(max(sum[i-1], sum[i-2] + arr[i]),

                     arr[i] + arr[i-1] + sum[i-3]);

    return sum[n-1];

}

http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

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.

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

    }