ここでは、最長増加部分列問題(LIS)について、 「プログラミングコンテストチャレンジブック（第2版）」（通称：蟻本）の p64, 65 を例に、python3 で実装する方法を紹介します。
まずはp64のDP(動的計画法)で実装する方法です。計算量はO(n^2)です。
# 入力
n = 5
a = [4, 2, 3, 1, 5]
#DPテーブル(0 で初期化)
dp = [0 for _ in range(n)]
def solve():
res = 0
for i in range(n):
dp[i] = 1
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)
res = max(res, dp[i])
print(dp)
return res
if __name__ == '__main__':
res = solve()
print(res)
続いてp65は、DP(動的計画法)の使用は同じですが、pythonのbisect_left() という関数を使用する方法です（蟻本ではC++の、lower_boundというSTL関数で実装されています）。計算量はO(n log n)です。
# 入力
n = 5
a = [4, 2, 3, 1, 5]
import bisect
INF = float('INF')
#DPテーブル(INF で初期化)
dp = [ INF for _ in range(n)]
def solve():
for i in range(n):
dp[bisect.bisect_left(dp, a[i])] = a[i]
print(dp)
if __name__ == '__main__':
solve()
print(bisect.bisect_left(dp, INF))