this can be done easily using dynamic programming:
dp[i] = a[i] + max( dp[i+2], dp[i+3], dp[i+4] , ... )
for (i=n-1 ; i>=0 ; i--)
{
max=0;
for (j=i+2 ; j<n ;j++)
if (dp[j]>max)
max=dp[j];
dp[i]=a[i]+max;
}
On 6/11/10, BALARUKESH <[email protected]> wrote:
> I hope using a backtracking solution suits the problem well...
> maxsum( int arr[] , int n,int i,int sum, int last)
> {
> if(i<n)
> {
> int s1= 0,s2= 0,s3;
> if(last ==i-1)
> {
> s1=maxsum(arr,n,i+2,sum,last);
> }
> else
> {
> s2= maxsum(arr,n,i+1,sum+arr[i],i);
> s3=maxsum(arr,n,i+2,sum,last);
> s2= s2>s3? s2 : s3 ;
> }
> s1= s1>s2? s1: s2;
> return s1;
> }
> return sum;
> }
>
> invoke the function initially as
>
> max= maxsum(arr,n,-2, 0, 0);
>
>
> Hope the program works...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
