//子串和子序列的區別是子串是連續的,子序列可以不連續
#include <iostream>
#include <vector>
using namespace std;
void MaxOrderedSub(const vector<int> &data)
{
int num=data.size();
//用輔助數組記錄以i結尾最長子串長度
vector<int> array(num,1);
for(int i=1;i<num;i++)
{
if(data[i]>data[i-1])
array[i]=array[i-1]+1;
}
int result=0;
int last=0;
//找到array中的最大值便是最長序列長
//last為這array中的下標,也就是最長序列的終點
for(int k=0;k<num;k++)
{
if(array[k]>result)
{
result=array[k];
last=k;
}
}
cout<<"the long of the sequence:"<<result<<endl;
cout<<"the sequence:"<<endl;
for(int j=last;array[j]!=1;j--);
for(i=j;i<=last;i++)
cout<<data[i]<<" ";
cout<<endl;
}
int main()
{
cout<<"input the size of the array:"<<endl;
int num;
cin>>num;
vector<int> arr(num,0);
for(int i=0;i<num;i++)
cin>>arr[i];
MaxOrderedSub(arr);
return 1;
}
作者“冒大煙的羊肉串的專欄”