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 <sbalarukesh1...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.