Alex Rivera | Logout

Algorithm to find the maximum subsequence of an array of positive numbers . Catch : No adjacent elements allowed

Asked 2009-02-25T00:11:30.957
16

For example, given

A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.

clearly max(oddIndexSum,evenIndexSum) does not work.

The main problem I have is that I can't come up with a selection criterion for an element. A rejection criterion is trivial given a selection criterion.

The standard maximum sub-sequence algorithm doesn't seem to be applicable here. I have tried a dynamic programming approach, but can't come up with that either. The only approach I could come up with was one that used a genetic algorithm.

How would you approach this?

arrays algorithm
Edit
Report

2 Answers

3
find_max(int t, int n)
{

     if(t>=n)
       return 0;
     int sum =0, max_sum =0;
     for(int i=t; i<n; ++i)
     {
       sum = sum + A[i];
       for(int j=i+2; j<n; ++j)
          sum = sum + find_max(A[j], n);
       if(sum > max_sum)
          max_sum = sum;
     }
     return max_sum;

}

The above is a recursive solution, have not compiled it. It's fairly trivial to see the repetition and convert this to a DP. Will post that soon.

answered 2011-01-12T23:59:27.977
0

While you used a bunch of fancy words, isn't this basically just a plain old graph problem of the travelling salesman?

Except in this case you are looking for the most expensive route through the (dense) graph? In this case the vertices are just the numbers themselves, the edges are not directed and have no weight, and all vertices are connected, except to the vertices that had been adjacent to them in the original list?

answered 2009-02-25T00:23:39.617

Your Answer