大佬们在leetcode的讲解—— 题目

题目描述

小明是蓝桥王国的骑士，他喜欢不断突破自我。

这天蓝桥国王给他安排了 N 个对手，他们的战力值分别为a1,a2,...,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。

身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。

请你算算小明最多会挑战多少名对手。

输入描述

输入第一行包含一个整数 N，表示对手的个数。

第二行包含 NN 个整数 a1,a2,...,an，分别表示对手的战力值。

1≤N≤3×10^5，1≤ai≤10^9。

输出描述

输出一行整数表示答案。

输入输出样例

示例 1

输入

1. 6
2. 1 4 2 2 5 6

输出

4

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

采用动态规划的方法，dp[i]表示选择nums[i]，并且以nums[i]结尾的最长上升子序列的长度。

设计两层循环，i：1～nums.length，j：0～i，如果nums[i] > nums[j]，则构成一个上升对，dp[i]就从dp[i], dp[j]+1两个种选择较大者，最后返回dp数组总的最大数

代码

1. def lengthOfLIS(nums):
2.     if not nums:
3.         return 0
4.     dp = []
5.     for i in range(len(nums)):
6.         dp.append(1)
7.         for j in range(i):
8.             if nums[i] > nums[j]:
9.                 dp[i] = max(dp[i], dp[j] + 1)
10.     return max(dp)
11. 
12. n=input()
13. nums=list(map(int,input().split()))
14. s=lengthOfLIS(nums)
15. print(s)