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.

Answer 2

Here is pure recursion implementation in swift:

// input is Array of (a,w), where a is element and w is weight

func lisw(input: [(Int, Int)], index:Int = 0, largestA:Int? = nil)->Int{
       guard index < input.count else { return 0 }

       let (a,w) = input[index]

       if a <= largestA {
          return lisw(input: input, index: index + 1, largestA: largestA)
       }

       let without_me = lisw(input: input, index: index + 1, largestA: largestA == nil ? a : largestA)
       let with_me = lisw(input: input, index: index + 1, largestA: a) + w

       return max(without_me,with_me)
}

Feel free to add memoization ;)