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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments