ZOJ2136解题报告
算法分析：这是个动态规划的问题，先求其子集，保存子集的结果，然后在子集的基础上再进行计算。此题要求最大升序子序列的长度，可以逆向考虑，先计算以第i个数为终点的最大升序子序列的长度，然后计算i后面的类似子序列。遍历的时候从首部开始，依次计算，最后求出最大的升序子序列。
数据结构：使用数组，vector.
代码实现：
#include <iostream>#include <vector>#include <cstring>using namespace std;struct num{ int index; int number; int longest;};int main(){ vector<num> v; num ele; int Nblock; int Nelement; int enumber; cin>>Nblock; for(int t = 0;t < Nblock;t++){ v.clear(); cin>>Nelement; for(int i = 0;i < Nelement;i++){ cin>>enumber; v.push_back(ele); v[i].index = i; v[i].number = enumber; if(i == 0){ v[i].longest = 1; continue; } int maxlongest = 0; for(int j = 0;j < i;j++){ if(v[j].number < enumber){ if(v[j].longest > maxlongest) maxlongest = v[j].longest; } } v[i].longest = maxlongest+1; } int k = 0; for(int p = 0;p < Nelement;p++){ if(v[p].longest > k) k = v[p].longest; } if(t != 0) cout<<endl; cout<<k<<endl; } return 0;}