算法至美

用户名：uq_54514514336

访问量：7737

签　名：

等　　级
排　　名	1360
经　　验	2948
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

[STL训练]sort练习-题解（各语言代码）
浏览：139

信息学奥赛一本通T1235-输出前k大的数-题解（各语言代码）
浏览：543

数列有序-题解（Python代码）
浏览：177

你可能喜欢

信息学奥赛一本通T1322-拦截导弹问题-题解（各语言二分法）

　　作者: 算法至美　　　　发表时间：2022-06-27 23:37:58 浏览：350　|　评论：0　

原题链接：信息学奥赛一本通T1322-拦截导弹问题

题意为求最长上升子序列
方法很多，这里提供一种高效的算法
时间复杂度O(n log n)，最坏空间复杂度O(n)
**python**
```python
from bisect import bisect_left
l=[float('inf')]
for i in map(int,input().split()):
	if i>l[-1]:l.append(i)
	else:l[bisect_left(l,i)]=i
print(len(l))
```
**C++**
```cpp
#include<vector>
#include<climits>
#include<iostream>
using namespace std;
int main(){
	vector<int>v(1,INT_MAX);
	for(int i;cin>>i;)
		if(i>v.back())v.push_back(i);
		else*lower_bound(v.begin(),v.end(),i)=i;
	cout<<v.size();
}
```
**java**
```java
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
	public static void main(String[] args) {
		final ArrayList<Integer> l = new ArrayList<>();
		l.add(Integer.MAX_VALUE);
		Arrays.stream(new Scanner(System.in).nextLine().split(" ")).mapToInt(Integer::parseInt).forEach(i -> {
			if (i > l.get(~-l.size())) l.add(i);
			else l.set(Math.abs(Collections.binarySearch(l, i) << 1 | 1) >> 1, i);
		});
		System.out.print(l.size());
	}
}
```

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

C二级辅导-统计字符（C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

数列（C++代码）

信息学奥赛一本通T1322-拦截导弹问题-题解（各语言二分法）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

Tom数（C++代码）

回文串（C语言代码）

【出圈】（C语言代码）

计算质因子（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

算法至美

TA的其他文章

你可能喜欢

C二级辅导-统计字符 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

数列 （C++代码）

信息学奥赛一本通T1322-拦截导弹问题-题解（各语言二分法）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

Tom数 （C++代码）

回文串 （C语言代码）

【出圈】 （C语言代码）

计算质因子 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-统计字符（C语言代码）

数列（C++代码）

　　评论区

Tom数（C++代码）

回文串（C语言代码）

【出圈】（C语言代码）

计算质因子（C++代码）