Given the list, you would never want to decrement the last element as you
want it to be the maximum.
so either retain or remove the last element
Lets consider the Minimum cost among the sequence i to j as Cost[i..j]
So if you remove the element j, you add j to the cost
Cost[i..j] = Min{ Min(cost[i..j-1])+j, SortByDecremet(Cost(i..j))}
in SortByDecrement returns the total cost of decrementing the elements i to
j-1 so that they are not greater than element j(such that the list is
non-decreasing).
If we solve this equation recursively then I think we will get the minmum
cost.
I hope this can be represented in a better way/better equation.
Correct me if anything is not taken care of .
On Tue, Apr 26, 2011 at 3:58 PM, snehal jain <learner....@gmail.com> wrote:
> @above
> you cant increment
>
>
> On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal <nav.coo...@gmail.com>wrote:
>
>> @snehal jain
>>
>> 4 9 8 7 8
>>> o/p 4 7 7 7 8
>>> cost 3 by decrementing 9 n 8
>>
>>
>> Yes, now question is clear but your last example is incorrect.
>>
>>
>> 4 9 8 7 8
>> o/p 4 8 8 8 8
>> cost 2 = decrementing (9 to 8) + incrementing (7 to 8)
>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
