if all the elements are positive then we can reverse the array and multiply
all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it gives
the answer for all k<=n with the minimum sum, this will be the answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja wrote:
> I thi
I think O(nlogn) solution is possible for this problem. First find the
largest increasing subsequence in O(nlogn) time.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>From this one u have LIS array M and parent array P. Now traverse through
the array M and for
