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 <[email protected]> wrote:
> thats right !
> DP must be the best approach to solve it !
>
>
>
> On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal <[email protected]
> > 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 <[email protected]>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 <
>>> [email protected]> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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.
