The LIS problem can be solved in `O(n \lg n)` time by defining the subproblem to store all the increasing subsequences in a compact way. The key idea is that if we have multiple increasing subsequence of length `k`, then we only need to store the one which ends in a smaller value.
Define `L[i]` to be the smallest possible value ending an increasing subsequence of length `k` for `A[1..i]`. `L[i]` can be considered to store `n` values, if there are no increasing subsequence of length `k`, then the smallest possible value at the end is `\infty`.
For example, for the sequence 50 5 100 10.
`L[1] = [50, \infty, \infty, \infty]`
`L[2] = [5, \infty, \infty, \infty]`
`L[3] = [5, 100, \infty, \infty]`
`L[4] = [5, 10, \infty, \infty]`
`L[i+1]` can be computed from `L[i]` in `O(\lg n)` time using binary search.
For more details, see http://www.cs.utoronto.ca/~brudno/csc2427/Lec9Notes.pdf
Prove that the greedy algorithm is optimal if in the penalty `g_{ij}` is raised to power 1.