300. Longest Increasing Subsequence

Find the longest increasing subsequence of a given sequence / array.

• Subsequence: a sequence derived from another by deleting some elements without changing order.

E.g.:
Input : [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Output : 6

Method 1 DP (N^2 time, N space):

• Compute the longest increasing subsequence ending at ith position ending at all i.
• Use answers ending on (i-1), (i-2), ... to find the answer on ith.
  • Look for the lis from previous computed results

def list(self, A):
    dp = [1] * len(A) #dp array to store computed results, base value is 1.
    for i in range(1, len(A)):
        for j in range(0, i):
            if A[j] < A[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return dp[i]

Method 2 DP(Nlog(n) time, 1 space)

tailsis an array storing the smallest tail of all increasing subsequences with lengthi+1intails[i].
For example, say we havenums = [4,5,6,3], then all the available increasing subsequences are:

len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
len = 3   :      [4, 5, 6]            => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Doing so will maintain the tails invariant. The the final answer is just the size.

def lengthOfLIS(self, nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) / 2
            if tails[m] < x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size

Follow up: Find a LIS that has the largest sum.

Method 1 DP (N^2 time, N space):

• For each entry in the dp list, store extra information about its sum along with its lis up to that point.
  • we can use a list: [[x1, y1],[x2,y2]] -> xi would be the lis up to i, yi would be the sum of LIS up to yi.

def lis(self, A):
    dp = [[1,i] for i in A] # sum from each position is at least its own value
    for i in range(1, len(A)):
        for j in range(0, i):
            if A[j] < A[i] and dp[i][0] <= dp[j][0]+1 and dp[i][1] < dp[j][1]+A[i]:
                dp[i][0], dp[i][1] = dp[j][0]+1, dp[j][1]+A[i]
    return max(dp, key=lambda x:x[1])[1]

dpLen[i] = maximum length of a LIS with maximum sum ending at i
dpSum[i] = maximum sum of a LIS with maximum sum ending at i

for i = 0 to n do
  dpLen[i] = 1
  dpSum[i] = input[i]

  maxLen = 0
  for j = 0 to i do
    if dpLen[j] > maxLen and input[j] < input[i]
      maxLen = dpLen[j]

  for j = 0 to i do
    if dpLen[j] == maxLen and input[j] < input[i] and dpSum[j] + input[i] > dpSum[i]
      dpSum[i] = dpSum[j] + input[i]

  dpLen[i] = maxLen + 1