最长上升子序列

O(n²)解法：

# 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)