最长上升子序列（动规）

 后面就根据之前学的动态规划的步骤往下走：

1.寻找子问题：

 其实就是前n个元素的最长子序列可能有多个序列有x个最长上升子序列，但是不是每一个序列的最后一个数都是比n+1个数下，所以会受到影响。

接下来换一个子问题的形式：

 2，确定状态：

 3，确定状态转移方程：

 解释一下：其实就是第k个数最大上升子序列的长度你可以遍历一下从1一直到k的数，看看如果第k个数更大的话，就在对应的maxlen的基础上加上1，因为从左到右遍历，所以这个数只会一直变大，直到找到最大的位置，但是我也在想，会不会有可能使得这个变小呢？我觉得应该不会，一直往右边走应该是会一直变大的（后面我自己看的时候这里有问题，因为代码里面有取max）。如果找不到相应的i的话，那就说明ak左边的数都是大于ak的所以这个位置就是一个最大上升子序列的开头。

#include 
#include 
#include 
using namesapce std;
const int MAX = 1010;
int a[MAX];
int maxlen[MAX];
int main(){
    int n,cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        maxlen[i] = 1;//一开始是把maxlen数组值都搞成1
    }
    for(int i = 2;i<=n;++i){
//这个i就是往前走的数
        for(int j = 1;j){
//这个j是i前面的数
            if(a[i]>a[j]){
                maxlen[i] = max(maxlen[i],maxlen[j]+1);
                //这个地方不能直接让maxlen[i] = maxlen[j]+1因为可能这个maxlen[i]之前有被更新了值超过了后面一个数。
            }
        }
    }
    cout<<*max_element(maxlen+1,maxlen+n+1);//这个函数是stl库里面的一个函数，这个可以求出maxlen数组里面的最大值。
    
    return  0;
} 

其实现在综合两题来看还是有很大的共同性的。都是会另外搞一个数组来存储子问题的解。然后状态转移方程的思路也差不多。还有一个要注意的点就是循环的范围选择了。其实找到规律和解题步骤也不是非常难。