Hi, probably you did'nt got my approach :
A={2,2,3,4,1,1,1,1,1}
first i=0 A[i] = 2
so candidates are A[1] ,A[2]
we choose max(A[1] +1 , 2 + A[2]) = A[2]
now we jump to A[2].
now candidates are A[3],A[4],A[5]
we choose max(A[3] + 3 , A[4] + 4, A[5] + 5)
= A[3]
so now we jump to A[3]
now candidates are A[4],A[5],A[6],A[7],
Clearly A[7] + 7 is maximum so we jump to A[7] and then we jump to
A[8]
so we went from 0->2->3->7->8.
Note i am not choosing max A[i] I am choosing max(i + A[i]).
Can anyone find a flaw in this approach ?
On Aug 11, 9:42 pm, Tharun Damera <tharun1...@gmail.com> wrote:
> Yes, greedy algo doesn't work.. U shud hv DP.. plz post the soln which u
> read..
> A={2,2,3,4,1,1,1,1,1}
>
> Ur algo gives 0,2,5,6,7,8(these are indices... index starts frm 0)
> best soln is 0,1,3,7,8..
>
> On Thu, Aug 11, 2011 at 2:37 PM, Arun Vishwanathan
> <aaron.nar...@gmail.com>wrote:
>
>
>
>
>
>
>
>
>
> > I did not get the optimal solution part..how is that u jump 1 to index 1?
>
> > On Thu, Aug 11, 2011 at 10:07 AM, Algo Lover <algolear...@gmail.com>wrote:
>
> >> Given an array, start from the first element and reach the last by
> >> jumping. The jump length can be at most the value at the current
> >> position in the array. Optimum result is when you reach the goal in
> >> minimum number of jumps.
>
> >> For ex:
> >> Given array A = {2,3,1,1,4}
> >> possible ways to reach the end (index list)
> >> i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
> >> 4)
> >> ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
>
> >> Since second solution has only 2 jumps it is the optimum result.
>
> >> My solution is for any index i loop from i to i + A[i]
> >> find an index j where
> >> (j + A[j]) is maximum for all j.
> >> make i=j;
>
> >> This solution in O(n) i suppose coz we are picking each element twice
> >> in the worst case.
>
> >> I have read a O(n^2) DP solution for this problem.....Is there any
> >> case where my approach will fail ?
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@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.
>
> > --
> > "People often say that motivation doesn't last. Well, neither does
> > bathing - that's why we recommend it daily."
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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.
>
> --
> D.Tharun| Computer Science and Engineering, IIT Bombay | tharu...@iitb.ac.in |
> +918097345806
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
