backtrack value which were chosen

Question

I have a c++ program which calculates maximum of a array provided no two consecutive elements of array can be taken. For eg: 7 3 4 6 will result in a answer of 13 .Here we chose 7 and 6 for optimal maximum. Here is my recursive program for it.

#include <iostream>
using namespace std;
int n;

int findMax(int x,int ar[])
{
    if(x < n)
        return max( ar[x]+findMax(x+2,ar), findMax(x+1,ar));
    return 0;

}

int main(){
    int ar[]={1,7,4,4,9,5,12};
    n = sizeof(ar)/sizeof(ar[0]);
    cout<<findMax(0,ar);
    return 0;
}

However I am more interested in the indices of array which were chosen for this purpose by my program .How can I do that efficiently. In the above program answer should be 1,4,6 as we chose 1st , 4th and 6th element of the array for the maximum.

Note: I am using 0 based indexing.

Thanks.

Answer 1

A recurrence relation R(k) for the maximum sum of the first k elements of the array (with no adjacent terms) is:

R(0) = 0, R(1) = max(0, a[0])
R(k) = max(a[k] + R(k-2), R(k-1))

This is almost the same recurrence you're using in your code, but in your code your function returns the maximum sum of elements k and later.

Anyway, you can build a table of these values in linear time using dynamic programming. In pseudocode:

R = new array of length n+1
R[0] = 0
R[1] = max(0, a[0])
for i = 2 .. n
   R[i] = max(a[i-1] + R[i-2], R[i-1])

If you just want the maximum sum, you can return R[n]. But you can also reconstruct the indices easily. In pseudo-code:

indices(a, R):
    result = new empty vector
    i = n
    while i > 0
        if (i == 1 and a[0] > 0) or R[i] == a[i-1] + R[i-2]
            result.push_back(i-1)
            i -= 2
        else
            i -= 1

You'll have to reverse result to get the indices in increasing order.