【dp-LIS】牛客网 --最长上升子序列 POJ 2533--Longest Ordered Subsequence（LIS模板题）

 牛客网 --最长上升子序列（LIS）&& POJ 2533--Longest Ordered Subsequence

题目链接1→牛客网 最长上升子序列   

题目链接2→POJ 2533 Longest Ordered Subsequence

 牛客网 --最长上升子序列（LIS）

       Problem Description

广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。 例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。

       Input

输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。
        紧接着第二行包含n个正整数m（1≤n≤10000），代表队伍中每位队员的身高。

       Output

 对应每一组数据，输出最长递增子序列的长度。

       Sample Input

7
1 7 3 5 9 4 8
6
1 3 5 2 4 6

       Sample Output

4
4

     

 POJ 2533--Longest Ordered Subsequence

       Problem Description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
        Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

        Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

       Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

        Sample Input

7
1 7 3 5 9 4 8

        Sample Output

4

       Problem Idea

解题思路:

【题意】

 本题要求的是最长上升子序列的长度；

【类型】
动态规划--最长上升子序列（LIS）
【分析】

本题的实质就是一个“最长上升子序列”的问题（LIS），刚开始我可能套用了一个假模板（其中ans=0），真正的应该ans=1；

若ans初值为0，当测试用例仅为1时，应输出1，实际上输出了0，不符合要求。

【时间复杂度】
O(n²)

 Source Code

#include <iostream>
using namespace std;
int a[10010];
int dp[10010];
int main() {
    int n;
    while(cin>>n&&n){
        for(int i=0;i<n;i++){
            cin>>a[i];
            dp[i]=1;
        }
        int ans=1; //注意当测试用例仅为1时，应输出1
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(a[j]<a[i]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
                ans=max(ans,dp[i]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}