Nopes solution is for only groups of size 2 and 3. solution is like a general DP
for string of length i to j there can be only 4 possibilities substring of length 2 from start + remaining string substring of length 3 from start + remaining string string except last 2 + value of last 2 string except last 3 + value of last 3 assign value that is max of all 4 but see what i got an O(N) solution http://ideone.com/KWIL2 it is giving answer same as in first O(N^2) so i hope it is correct it is like coin denomination easy to get :) On Fri, Jul 8, 2011 at 3:29 AM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote: > Can u explain ur algo too?? > > On 7/8/11, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > > @Sunny...nice solution but ur solution works if there can 1 to 3 > > groups of digits..but in the question its mentioned the group should > > contain exactly 2 or 3 digits... > > > > but anyways nice solution...:) > > > > On 7/8/11, sunny agrawal <sunny816.i...@gmail.com> wrote: > >> http://ideone.com/xv73J > >> > >> > >> On Fri, Jul 8, 2011 at 2:16 AM, Piyush Sinha > >> <ecstasy.piy...@gmail.com>wrote: > >> > >>> @Sunny...can u post a definite algo for it?? > >>> > >>> On 7/8/11, Ravi Shukla <shuklaravi...@gmail.com> wrote: > >>> > @sunny , yep it looks DP. more of MCM. > >>> > > >>> > solve for substrings of length 1,2,3. > >>> > and then apply DP[i][j]=max score for a substring from i to j. > >>> > =max(DP[i][k]+DP[k][j]) where k>i && k<j . > >>> > > >>> > The complexity this approach renders would be O(n^3). > >>> > with O(n^2) space complexity. > >>> > > >>> > anyone anything better ? > >>> > > >>> > Thanks. > >>> > Ravi Shukla > >>> > CSE Final Year. > >>> > BIT Mesra, Ranchi > >>> > > >>> > -- > >>> > 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. > >>> > > >>> > > >>> > >>> > >>> -- > >>> *Piyush Sinha* > >>> *IIIT, Allahabad* > >>> *+91-8792136657* > >>> *+91-7483122727* > >>> *https://www.facebook.com/profile.php?id=100000655377926 * > >>> > >>> -- > >>> 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. > >>> > >>> > >> > >> > >> -- > >> Sunny Aggrawal > >> B-Tech IV year,CSI > >> Indian Institute Of Technology,Roorkee > >> > >> -- > >> 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. > >> > >> > > > > > > -- > > *Piyush Sinha* > > *IIIT, Allahabad* > > *+91-8792136657* > > *+91-7483122727* > > *https://www.facebook.com/profile.php?id=100000655377926 * > > > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=100000655377926 * > > -- > 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. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
