@Piyush: Hmmm. Children of i = 0, l = 0 are a[0+0+1] and a[0+0+2]. Check. Children of i = 0, l = 1 are not a[0+1+1] and a[0+1+2]; they are a[3] and a[4]. Am I missing something?
Dave On Nov 4, 11:00 pm, piyush rai <[email protected]> wrote: > there is a better way to get a child of node at index i and level l > The child will always be @ index (i+l+1) and (i+l+2) then solve recursively > keeping and array of length of level, top-down approach OR do a bottom up > approach without using any extra memory. > > > > On Fri, Nov 5, 2010 at 9:01 AM, Dave <[email protected]> wrote: > > @juver++: Oops. Right you are! A corrected solution is just a little > > more complicated. If the data is presented in an array as in the > > previous posting, a[]={1,2,3,4,5,6,7,8,9,10} corresponding to the > > triangle > > 1 > > 2 3 > > 4 5 6 > > 7 8 9 10 > > then we let A(i,j) be the jth entry in the ith row, both 0-based, so > > that in this example, A(2,1) = 5Then the array can be treated as an > > implicit DAG (directed acyclic graph) where the children of A(i,j) are > > A(i+1,j) and A(i+1,j+1). Using the correspondence that A(i,j) = a[i*(i > > +1)/2+j)], you can traverse the DAG the same way I described > > traversing the binary tree. > > > Dave > > > On Nov 4, 3:19 pm, "juver++" <[email protected]> wrote: > > > You are wrong. It's not a binary tree. Cause multiple elements have > > > adjacent childs. > > > Right solution is to apply DP: > > > dp[i][j] - maximum sum that is ends into i-th row and j-th column. > > > Then make only 2 transitions to the (i+1)-th row. > > > Complexity is n^2. > > > > On Nov 4, 7:50 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.- Hide quoted text - > > > > - Show quoted text - > > > -- > > 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%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
