Maximum Weight Increasing Subsequence

Question

In the Longest Increasing Subsequence Problem if we change the length by weight i.e the length of each element A_i is 1 if we change it to W_i How can we do it in O(NlogN).

For Example For an array of 8 Elements

Elements 1  2  3  4  1  2  3  4
Weights  10 20 30 40 15 15 15 50 

The maximum weight is 110.

I found the LIS solution on wikipedia but I can't modify it to solve this problem.

Answer 1

Still, we use f[i] denotes the max value we can get with a sequence end with E[i].

So generally we have for (int i = 1;i <= n;i++) f[i] = dp(i); and initially f[0] = 0; and E[0] = -INF;

Now we shall calculate f[i] in dp(i) within O(log(N)).

in dp(i), we shall find the max f[j] with E[j] < E[i] for all 0 <= j < i. Here we can maintain a Segment Tree.

So dp(i) = find_max(1,E[i]-1) + W[i](this takes O(log)), and for every f[i] already calculated, update(E[i],f[i]).

So the whole algorithm takes (O(NlogN)).

Tip: If E[i] varies in a very big range, it can be Discretizationed.