Mdoify LIS Such that a element is greater than sum of all elements before

Question

Suppose an array = {2,5,7,8,10}. You need to find the length of Longest Increasing Sub-sequence such that a element is not less than the sum of all elements before it.

In this case the answer can be {2,5,7}, {2,5,8} or {2,8,10}. So Length = 3
This is easily solvable in O(n^2). As LIS Length can be found in O(n log n). As the problem is asking only the length, so, I think this problem is also solvable in O(n log n). But how can I do that?

Answer 1

Actually you don't need a DP Solution at all.
First sort the numbers in non-decreasing order. And loop from left to right. keep track of the current sum.
If next number is not-less than the sum add it to LIS. else proceed to next number.
It can be proven that the greedy solution is the optimal solution. Prove it yourself ;)

Answer 2

1. There's an O(N^2) dynamic programming solution which goes like:

   • Let f(i, j) be the smallest sum that a "correct" subsequence ending in one of the first i elements and consisting of exactly j elements can have.

   • The base case is f(0, 0) = 0 (empty prefix, no elements)

   • The transition are f(i, j) -> f(i + 1, j) (not adding a new element) and
     f(i, j) -> f(i + 1, j + 1) if a[i] > f(i, j) (adding the i-th element to the end of the subsequence if we can).

The correctness of this solution is self-evident.

2. A cool fact: let A be a "correct" subsequence of k elements. Than the last element of A is not less than max(1, 2^(k-2))(proof: it's the case for k = 1 and k = 2. Now we can use induction and the fact that 1 + sum i = 0 .. k of 2^k = 2^(k+1))

3. Thus, j ranges over 0..log MAX_A + C in the dynamic programming solution described above, so it works in O(N * log MAX_A).

O(N * log MAX_A) is not O(N log N), but this solution can be good for practical purposes.