暴力算法

import random

def lis_recursive(arr, i):
if i == len(arr) - 1:
return 1
max_len = 0
for j in range(i + 1, len(arr)):
if arr[j] > arr[i]:
length = lis_recursive(arr, j)
if length > max_len:
max_len = length
return max_len + 1

def lis_bruteforce(arr):
max_len = 0
for i in range(len(arr)):
length = lis_recursive(arr, i)
if length > max_len:
max_len = length
return max_len


动态规划

def lis_dp(arr):
max_len = 0
dp = [1 for j in range(0, len(arr))]
for i in range(len(arr) - 2, -1, -1):
for j in range(i + 1, len(arr)):
if arr[i] < arr[j]:
dp[i] = max(dp[j] + 1, dp[i])
max_len = max(max_len, dp[i])
return max_len


二分查找法

def bin_search(arr, start, end, key):
while start <= end:
mid = (start + end) // 2
if key <= arr[mid]:
end = mid - 1
else:
start = mid + 1
return start

def lis_bin_search(arr):
min_ends = [0 for i in range(len(arr))]
min_ends[0] = arr[0]
length = 1
for i in range(1, len(arr)):
pos = bin_search(min_ends, 0, length - 1, arr[i])
min_ends[pos] = arr[i]
if pos == length:
length += 1
return length


测试

arr = [3, 0, 2, 1, 4]
print(lis_bruteforce(arr))
print(lis_dp(arr))
print(lis_bin_search(arr))

for i in range(0, 100):
arr = [random.randint(0, 9) for i in range(10)]
result1 = lis_bruteforce(arr)
result2 = lis_dp(arr)
result3 = lis_bin_search(arr)
if result1 != result2 or result2 != result3:
print(result1, result2, result3)

3
3
3


性能测试

import timeit
import random

def test_lis_bruteforce():
length = random.randint(1, 100)
arr = [random.randint(0, 10) for i in range(length)]
lis_bruteforce(arr)

def test_lis_dp():
length = random.randint(1, 100)
arr = [random.randint(0, 10) for i in range(length)]
lis_dp(arr)

def test_lis_bin_search():
length = random.randint(1, 100)
arr = [random.randint(0, 10) for i in range(length)]
lis_bin_search(arr)

print(timeit.timeit(test_lis_bruteforce, number=10, setup='from __main__ import test_lis_bruteforce'))
print(timeit.timeit(test_lis_dp, number=10, setup='from __main__ import test_lis_dp'))
print(timeit.timeit(test_lis_bin_search, number=10, setup='from __main__ import test_lis_bin_search'))

2.092267832995276
0.005408962009823881
0.0011912080080946907