The example I did by hand was { 3,7,2,1 }. Here the answer is 8. My code I ran on 2,5,7,1,8,9. This produces 18 if you run it. See http://codepad.org/FW0Y4rL7 .
Both are correct as far as I can see. Sorry for the confusion. On Oct 9, 12:56 am, Lego Haryanto <legoharya...@gmail.com> wrote: > I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 } > should be 18, right? > > > > > > On Thu, Oct 7, 2010 at 10:53 PM, Anand <anandut2...@gmail.com> wrote: > > Using standard Dynamic Programing logic: > >http://codepad.org/IwBTor4F > > > On Thu, Oct 7, 2010 at 8:43 PM, Gene <gene.ress...@gmail.com> wrote: > > >> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes. > >> Let F(i,j) be the maximum possible score the current player can get > >> using only notes i through j. Then > > >> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) ) > > >> This is saying that the current player always makes the choice that > >> minimizes B the best score that the other player can achieve. When we > >> know that choice, the best _we_ can do is the sum of all the available > >> notes minus B. > > >> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j) > >> where i > j. > > >> For example, suppose we have notes 3 7 2 1 . The answer we want is > >> F(1,4). > > >> Initially we have > >> F(1,1) = 3 > >> F(2,2) = 7 > >> F(3,3) = 2 > >> F(4,4) = 1 > > >> Now we can compute > >> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7). > >> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7). > >> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2). > >> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care). > >> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7). > >> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1). > > >> On Oct 7, 8:14 pm, Anand <anandut2...@gmail.com> wrote: > >> > Given a row of notes (with specified values), two players play a game. > >> At > >> > each turn, any player can pick a note from any of the two ends. How will > >> the > >> > first player maximize his score? Both players will play optimally. > > >> -- > >> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) -- 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.