博客

题目描述

题目描述

Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？

样例输入

6

2 5 1 5 4 5

样例输出

3

提示

Example:

6个点的高度各为 2 5 1 5 4 5

如从第1格开始走,最多为3步, 2 4 5

从第2格开始走,最多只有1步,5

而从第3格开始走最多有3步,1 4 5

从第5格开始走最多有2步,4 5

所以这个结果是3。

接口说明

方法原型：

int GetResult(int num, int[] pInput, List  pResult);

输入参数：

int num：整数，表示数组元素的个数（保证有效）。

int[] pInput: 数组，存放输入的数字。

输出参数：

List pResult: 保证传入一个空的List，要求把结果放入第一个位置。

返回值：

正确返回1，错误返回0

输入描述:

输入多行，先输入数组的个数，再输入相应个数的整数

输出描述:

输出结果

示例1

输入

6

2

5

1

5

4

5

输出

3

方法一：动态规划

每次都向前找比它小的以及比它大的位置，将第一个比它大的替换掉，这样操作虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的。

此题可用动态规划求解，a[i]表示以nums[i]为结尾的最长子序列长度，遍历num[i]之前的数并更新a[i]的值

此算法的复杂度为n2

while True:
    try:
        n=int(input())
        nums=[int(i) for i in input().split()]
        a = [1] * len(nums)
        if len(nums) == 0:
            print(0)
        for i in range(1, len(nums)):
            for j in range(0, i):#每次向前找比它小的
                if (nums[i] > nums[j]):
                    a[i] = max(a[i], a[j] + 1)#a[i]表示以nums[i]为结尾的最长子序列长度
        print(max(a))
    except:
        break

方法二：二分查找

遇到插入索引等于当前列表长度的，即大的元素，添加；否则更改插入索引位置的数字

import bisect#二分查找的库
while True:
    try:
        n=int(input())
        nums=[int(i) for i in input().split()]
        a = []
        if len(nums)==0:
            print(0)
        for i in nums:
            position = bisect.bisect_left(a, i)#在a中插入i应插入的位置index，排序；若i已存在，则返回左边的位置index
            if len(a)==position:#第一个元素，或者大于a中元素的元素才插入
                a.append(i)
            else:
                a[position]=i#否则替换对应index的值
        print(len(a))
    except:
        break

参考：

https://blog.csdn.net/Tianchi_M/article/details/82691277