Thanks, I think that will work :) On Thu, Nov 4, 2010 at 10:20 PM, Dave <[email protected]> wrote:
> @Piyush: Treat the data as an implicit binary tree, with the children > of a[i] being a[2*i] and a[2i+1] if a[] is a 1-based array, or a[2*i > +1] and a[2*i+2] if a[] is a 0-based array. Traverse the tree and > accumulate the sum as you descend. When you reach the leaves, keep > track of the maximum sum and its path. When the traversal is finished, > you will have your answer. > > Dave > > On Nov 4, 4:47 am, Piyush <[email protected]> wrote: > > Given an array of integers. Imagine it as a pyramid as below: > > a[]={1,2,3,4,5,6,7,8,9,10} > > 1 > > 2 3 > > 4 5 6 > > 7 8 9 10 > > find a path from level 1 to last level such that the sum is maximum. > > The path is such that its children should be reachable. > > Eg: > > 1,2,5,9 is a path > > 1,2,6,10 is not a path since 6 is not reachable from 2. > > The array is not sorted and numbers are random. > > -- > 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]<algogeeks%[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.
