Find Max Sum

Problem: Given an array all of whose elements are 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. For example,

• 3 2 7 10 should return 13 (sum of 3 and 10)
  
• 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

Solution:read

#include <iostream>
using namespace std;

void findMaxSum(int buf[], size_t cnt);
void findMaxInterlacedSum(int *buf, size_t cnt);

/**
 ******************************************************************************
 *
 * Given an array all of whose elements are 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. For example,
 *
 * i) 3 2 7 10 should return 13 (sum of 3 and 10)
 * ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7) 
 * 
 * Reference:
 * http://stackoverflow.com/questions/584228?sort=newest#sort-top
 *
 * @param argc 
 * @param argv 
 * 
 * @return int 
 *
 ******************************************************************************
 */
int main (int argc, char *argv[])
{
    int array1[] = { 3, 2, 7, 10 };
    int array2[] = { 3, 2, 5, 10, 7 };
    int array3[] = { 3, 7, 2, 10, 9, 1 };

    findMaxInterlacedSum(array1, sizeof(array1)/sizeof(int));
    findMaxInterlacedSum(array2, sizeof(array2)/sizeof(int));
    findMaxInterlacedSum(array3, sizeof(array3)/sizeof(int));

    cout << endl << "findMaxSum . . ." << endl;

    findMaxSum(array1, sizeof(array1)/sizeof(int));
    findMaxSum(array2, sizeof(array2)/sizeof(int));
    findMaxSum(array3, sizeof(array3)/sizeof(int));

    return(0);
}

/**
 ******************************************************************************
 *
 * Finds maximum sum from any numbers as long as they are not adjcent numbers. 
 * 
 * @param buf 
 * @param cnt 
 *
 ******************************************************************************
 */
void findMaxSum(int buf[], size_t cnt)
{
    int incl = 0;   // max sequence including the previous item
    int excl = 0;   // max sequence excluding the previous item
    int excl_new=0;

    for (size_t i = 0; i < cnt; i++)
    {
        //cout << buf[i] << ", " << ((i+1 < cnt) ? buf[i+1] : 0) << ", ";

        // current max excluding i
        if (incl > excl)
        {
            excl_new = incl;
        }
        else
        {
            excl_new = excl;
        }

        // current max including i
        incl = excl + buf[i];
        excl = excl_new;

        //printf("incl=%d, excl=%d, excl_new=%d\n", incl, excl, excl_new);
    }
    cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}

/**
 ******************************************************************************
 *
 * Finds maximum sum in an interlaced fashion. 
 * 
 * @param buf 
 * @param cnt 
 *
 ******************************************************************************
 */
void findMaxInterlacedSum(int *buf, size_t cnt)
{
    int sumE = 0;
    int sumO = 0;

    for (size_t i=0; i < cnt; i+=2)
    {
        cout << buf[i] << ", " << ((i+1 < cnt) ? buf[i+1] : 0) << ", ";

        sumE += buf[i];
        if (i+1 < cnt) sumO += buf[i+1];
    }
    cout << "\nmax interlaced sum = " << ((sumE > sumO)? sumE : sumO) << endl;
}
// This solution is kindly provided by Jeff Fore.
hide solution