O(n2)解法：
# coding: utf-8
import sys
def LIS(arr):
"""
O(n^2)
:param arr:
:return:
"""
dp = [0] * len(arr)
max_len = 0
for i in range(len(arr)):
dp[i] = 1
for j in range(i):
if arr[j] <= arr[i] and dp[j] + 1 >= dp[i]:
dp[i] = dp[j] + 1
max_len = max(dp[i], max_len)
print(max_len)
if __name__ == "__main__":
arr = [1, -2, 3, 10, -4, 7, 2, -5]
find_max_sub_sum(arr)
O(n*logn)
# coding: utf-8
import sys
def find_position(arr, left, right, key):
"""
二分查找
:param arr:
:param left:
:param right:
:param key:
:return:
"""
if arr[right] <= key:
return right + 1
while left < right:
mid = (left + right) // 2
if arr[mid] <= key:
left = mid + 1
else:
right = mid
return left
def LIS_improved(arr):
"""
O(nlogn)
:param arr:
:return:
"""
record = [0] * len(arr) # record[i]表示长度为i的LIS结尾元素的最小值
record[0] = arr[0]
max_len = 0
for i in range(1, len(arr)):
insert_index = find_position(record, 0, max_len, arr[i])
record[insert_index] = arr[i]
if insert_index > max_len:
max_len = insert_index
print(max_len + 1)
if __name__ == "__main__":
lis_arr1 = [2, 7, 1, 5, 6, 4, 3, 8, 9]
lis_arr2 = [3, 1, 2, 6, 4, 5, 10, 7]
LIS_improved(lis_arr1)
LIS_improved(lis_arr2)
