【LIS】【严格递增和非严格递增】

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;

int a[10] = {0,1,5,3,6,9};
vector<int> v;
int main()
{
	v.clear();
	v.push_back(a[1]);
	for(int i=2;i<5;i++)
	{
		if(a[i] > v.back())
		{
			v.push_back(a[i]);
		}
		else
		{
			*lower_bound(v.begin(),v.end(),a[i]) = a[i];
		}
	}
	cout << v.size() << endl;
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;

int a[10] = {0,1,5,3,3,6,9};
vector<int> v;
int main()
{
	v.clear();
	v.push_back(a[1]);
	for(int i=2;i<6;i++)
	{
		if(a[i] >= v.back())
		{
			v.push_back(a[i]);
		}
		else
		{
			*lower_bound(v.begin(),v.end(),a[i]) = a[i];
		}
	}
	cout << v.size() << endl;
}