最长不下降子序列（Onlogn算法）

Question

最长不下降子序列（Onlogn算法）

Description
一个数的序列bi，当b1 <= b2 <= ... < =bS的时候，我们称这个序列是不下降的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些不下降的子序列(ai1, ai2, ..., aiK)，这里1<= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些不下降子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

Input
多组case， 每组case两行：
第一行 输入一个数 n (n < 10000)， 表示有n个数
第二行 n个数， 分别代表每个数；

Output
每个case一行 输出 该数列的最长的长度 ；

Sample Input
7
1 7 3 5 9 4 8

Sample Output
4

Answer 1

int main()
{
    vector<int> nums{ 1 ,7, 3, 5, 9, 4, 8 };   
    int s = nums.size();
    vector<int> dp(s,1);
    int result = 1;
    for (int i = 1; i < s; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        result = max(dp[i], result);
    }
    cout << result;
    return 0;
}