int solve(int lo, int hi) { // lo = 0, and hi = length - 1 in initial pass if(lo==hi) return a[lo]; int &d = dp[lo][hi]; if(~d) return d; // dp array initialized with {-1} d = -INF; for(int i=lo;i<hi;i++) { d = max(d, solve(lo, i) + solve(i+1, hi)); d = max(d, solve(lo, i) * solve(i+1, hi)); } return d; }
On Wed, Dec 1, 2010 at 12:14 AM, Algoose chase <harishp...@gmail.com> wrote: > thats right ! > DP must be the best approach to solve it ! > > > > On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal <akash.agrawa...@gmail.com > > wrote: > >> In addition to these assumptions, you have also assumed that numbers are >> greater than 1 else * will lower the result. >> >> Regards, >> Akash Agrawal >> http://tech-queries.blogspot.com/ >> >> >> >> On Thu, Nov 25, 2010 at 11:18 AM, Algoose chase <harishp...@gmail.com>wrote: >> >>> For this specific case since only 2 operators are used : + , * and >>> we know that * is the operator that maximizes the value(provided both the >>> operands are not equal to one / none of the operand is zero and also given >>> that operands are +ve ). >>> Doing * operation as late as possible should suffice right ? >>> >>> For Eg: Do all additions in the first pass and do all multiplications in >>> 2nd pass. >>> >>> is there be any case where the above mentioned logic fails ? >>> >>> On Wed, Nov 24, 2010 at 4:07 PM, Amir hossein Shahriari < >>> amir.hossein.shahri...@gmail.com> wrote: >>> >>>> you can use an algorithm similar to matrix chain multiplication i.e. if >>>> dp[i][j] is the maximum value that you can get with the numbers v_i to v_j >>>> and in order to maximize it find k that maximizes ( dp[i][k] op_k >>>> dp[k][j] >>>> ) >>>> v_i is the ith value and op_k is the kth operator >>>> obviously if i==j : dp[i][j] = v_i >>>> >>>> -- >>>> 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. >>> >> >> -- >> 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. > -- 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.