Sunday, January 2, 2011

Maximum sub array revisited !!!

Given an array of positive numbers, find the maximum sum of a subsequence such that no 2 elements in the sequence should be adjacent in the array.
For e.g
For an array  3 2 5 10 7 function should return 15


If we figure out all the combinations in which no two elements are adjacent and pick the maximum sum, our job would be done.
A simple recursive algorithm would perform the job

int maxSum(int *a, int size, int idx, int sum) {
    if (idx >= size)
        return 0;
    return max (maxSum(a, n, idx + 1), a[idx] + maxSum(a, n, idx + 2));

But wait how about the complexity? The order would be equal to number of combination processed, which would be exponential in nature.

So how do we reduce it? If we observe carefully many of the subproblems are repeated and computed over and over (To gain more insight on the repeating subproblems refer this link). 
Indeed it is a dynamic programming problem and storing the results of the subproblems would improve the complexity considerably. 

Below is short snippet code for the same

int maxSum(int *a, int size, int idx, int sum) {
    if (idx >= size)
        return 0;
    if (mem[idx + 1] == 0)
        mem[idx + 1] = maxSum(a, n, idx + 1);
    if (mem[idx + 2] == 0)
        mem[idx + 2] = maxSum(a, n, idx + 2);

    return max (mem[idx + 1], a[idx] + mem[idx + 2]);


  1. O(n^2):

    best[i] = max(best[0], ..., best[i-1], best[i-2]) + input[i]

    answer is max(best)

    which i think that can be reduced to O(n):

    best[i] = max(best[i-2], best[i-3]) + input[i], because all elements are positive, thus at least one of three consecutive elements should be chosen.

  2. @imavalon ... no extra space and O(n).....

  3. do the same as my O(n) approach, but keep best[i-1] best[i-2] and best[i-3] on two temporary variables:

    int best, best_0, best_1, best_2, best_3;
    for(int i = 0; i < input.length; i++){
    best_3 = best_2;
    best_2 = best_1;
    best_1 = best_0;
    best_0 = max(best_2, best_3) + input[i];
    best = max(best, best_0);
    return best;