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?
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 ;)