左老师的爱
Description:
左老师有n个题目，他希望出一张考试试卷，从中选取一定数量的题目，在不改变给定题目顺序的情况下，要求选取的题目难度严格递增，为了防止有人AK，左老师希望在考试中出尽可能多的题目，求最大题目数量。
Input:
每个测试点只有一组测试数据。
第一行一个整数n表示题目数量，第二行n个整数ai表示题目难度。
测试点
Output:
输出一个整数ans，一场考试中题目数量的最大值
Sample Input:
5
1 2 3 1 5
Sample Output:
4
Hint:
可以选取第1、2、3、5题
解题分析：
分析问题后可以发现，这是一个求最长上升子序列的问题。
一、简单一般的动态规划法：
#include <iostream>
using namespace std; int arr[100005];
int lis(int arr[],int n)
{ int longest[n]; for (int i=0; i<n; i++) longest[i] = 1; for (int j=1; j<n; j++) { for (int i=0; i<j; i++) { if (arr[j]>arr[i] && longest[j]<longest[i]+1){ //注意longest[j]<longest[i]+1这个条件，不能省略。 longest[j] = longest[i] + 1; //计算以arr[j]结尾的序列的最长递增子序列长度 } } } int max = 0; for (int j=0; j<n; j++) { //cout << "longest[" << j << "]=" << longest[j] << endl; if (longest[j] > max) max = longest[j]; //从longest[j]中找出最大值 } return max;
} int main()
{ int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++){scanf("%d",&arr[i]);}int ret = lis(arr,n); cout << ret << endl; }return 0;
} 显然这是O(n^2)的算法，但是当n到1e5的时候，会超时，需要优化。
二、最长上升子序列nlogn算法
来源于学长：https://blog.csdn.net/shuangde800/article/details/7474903
和博主：https://blog.csdn.net/yopilipala/article/details/60468359
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{int n,num[100100],lis[100100],len;while(scanf("%d",&n)!=EOF){len = 0;memset(lis,0,sizeof(lis));for(int i=0;i<n;i++)//如果i是从1开始，在lower_bound中的到的位置会返回到0，这样就不可以把lis[1]的位置替换掉，从而WA。{scanf("%d",&num[i]);}lis[0] = num[0];for(int i=1;i<n;i++){if(num[i] > lis[len])//如果num比lis[len]选择的终点大，则可以放入lis，即新的终点。lis[++len] = num[i];else{int pos = lower_bound(lis,lis+len,num[i]) - lis;//注意lower_bound 的用法，lower_bound返回的是一个地址lis[pos] = num[i];//！！！}}printf("%d\n",len+1);//len是从0开始的，所以要加上1。}
}这个算法的分析：
自己手动跟着算法跑一遍会比较清楚，这里想提出我对这个算法的发现。
1.lis[i] (i从0开始)数组里其实存储的是，长度为i+1的、最靠后的、最长上升子序列的最末的值，也就是以lis[i]结尾。
2.以序列2 1 5 3 6 4 8 9 7为例
最终lis[]数组为1 3 4 7 9。
当扫描到9，还没扫描到7时，lis[]数组为1 3 4 8 9。9在lis[4]这个位置上，继续处理到7，其实如果7这个位置的数比9大，lis里应该添在9之后，并且最长序列的长度应该为5。但是7比9小，这个时候就要用二分搜索，搜索lis数组，位置前移去替代lis里的数，每往前一个表示以7结尾的长度并没有那么长。
upper_bound()与lower_bound()使用方法:
二分搜索函数，头文件为<algorithm>，要求查找的序列应为有序序列。
是模版函数，使用范围很广，算法题中主要用于数组的二分查找。
参数：开始地址、结束地址、比较的元素
数组返回值：
upper_bound返回第一个大于的元素的下标；
lower_bound返回第一个大于等于元素的下标；
#include <iostream>
#include <algorithm>//必须包含的头文件
using namespace std;
int main()
{int point[10] = {
1,3,7,7,9};int a = upper_bound(point, point+5, 7) - point;//按从大到小搜索，7最后能插入数组point的哪个位置 int b = lower_bound(point, point+5, 7) - point;按从小到大搜索，7最早能插入数组point的哪个位置 cout<<a<<endl;cout<<b<<endl;return 0;
}output:
4
2
memset()函数用法：
#include<cstring>
#include<iostream>
using namespace std;
int main()
{int lis[5];memset(lis,0,sizeof(lis));memset(lis,-1,sizeof(lis));int a,b;a=sizeof(lis)*5;cout<<a<<endl;b=sizeof(lis);cout<<b<<endl;for(int i=0;i<5;i++){cout<<lis[i]<<endl;}return 0;} 结果：
第一个参数是开始地址，第二个参数是设置为0或-1（只有这两个值），第三是字节大小
第三个参数应该是：sizeof(lis)，而不是sizeof(lis)*5