LIS

27 May 2023 in Study / Computer science on Lis

Algorithm, DP, Binary Search

• Longest Increasing Subsequence
• ex [10, 16, 8, 20, 7, 21]
  • LIS : [10, 16, 20, 21]

Method 1

• Use DP
• O(N²)
• Meaning of dp[i] : Length of LIS that ith element gonna be last element
• Python
  

l = [10, 16, 8, 20, 7, 21]
dp = [0] * 6
dp[0] = 1

for i in range(1, len(l)):
  maxLength = 1
  for j in range(i):
    if l[i] > l[j]:
      maxLength = max(maxLength, dp[j] + 1)
  dp[i] = maxLength

print(max(dp))

Method 2

• Use Binary Search
• O(NlogN)
• Python
  

import bisect

l = [1, 6, 3, 4, 2, 8, 12, 9, 13, 14, 12]
process_lis = [l[0]]

for i in range(1, 11):
    if l[i] > process_lis[-1]:
        process_lis.append(l[i])
    else:
        index = bisect.bisect_left(process_lis, l[i])
        process_lis[index] = l[i]

maxLength = max(dp)
print(maxLength)

※ process_LIS != LIS

Get LIS

• how to solve LIS (not length)
• Use dp (has same meaning with dp in method1)
• Python
  

import bisect

l = [1, 6, 3, 4, 2, 8, 12, 9, 13, 14, 12]
process_lis = [l[0]]
dp = [0] * 11
dp[0] = 1

for i in range(1, 11):
    if l[i] > process_lis[-1]:
        process_lis.append(l[i])
        dp[i] = len(process_lis)
    else:
        index = bisect.bisect_left(process_lis, l[i])
        process_lis[index] = l[i]
        dp[i] = index + 1   

maxLength = max(dp)
maxIndex = dp.index(maxLength)
print(maxLength)

lis = [l[maxIndex]]
difference = 1

for i in range(maxIndex - 1, -1, -1):
    if dp[i] + difference == maxLength:
        lis.append(l[i])
        difference += 1

for i in range(len(lis)):
    print(lis[len(lis) - i - 1], end = " ")

Reference

Method 1, 2
Get LIS