LIS.学习C++ 最长上升序列

给一串数 33 4 2 324  44 55  最长上升的序列是 33 44 55 值为3 序列不唯一 长度是唯一的

怎么搞喃 弄一个dp[max]数组 存放到达每个位置时候的最长序列

for(int i=1;i<len;i++)

 for(int j=0;j<i;j++)

  {

if(a[j]<a[i]&&dp[j]+1>dp[i] )

dp[i]=dp[j]+1;

 }酱紫就把整个DP都处理好了。直接输出最大的那个就可以了。

来完整马

#ifndef H_HPP#define H_HPP#include <iostream>#include <string>using namespace std;template<typename T>class A{	string str;	int dp[111];public:		A(const string &s);	~A(){};};template<typename T>A<T>::A(const string &s) :str(s){	for (int i = 0; i < 100; i++)		dp[i] = 1;//每个dp至少为1嘛 	int ans = 1;	for (int i = 1; i < str.size(); i++)	{					for (int j = 0; j < i;j++)			{				if (str[j]<str[i]&&dp[j]+1>dp[i])//a j比a i小而且 他dp+1大于dp[i]才可以更新i的dp值			{				dp[i] = dp[j] + 1;			}			 }		if (dp[i] > ans)ans = dp[i];//这里记录当前为止最大的值			}	for (int i = 0; i < str.size(); i++)		cout << dp[i] << " ";}#endif //H_HPP
#include "h.hpp"int main(){	A<int>a("9394397");	system("pause");}嗯就是这样