【C++】洛谷B3637最长上升子序列-创新互联

这是一个简单的动规板子题。

给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

第一行，一个整数 n n n，表示序列长度。

第二行有 n n n 个整数，表示这个序列。

一个整数表示答案。

6
1 2 4 1 3 4

4

分别取出 1 1 1、 2 2 2、 3 3 3、 4 4 4 即可。

思路： 用dp[i]表示序列中第i个元素处的最长上升子序列，那么如果想知道dp[i]的值，则需要找到第i个元素之前的最长上升子序列且此子序列的大元素不能比当前元素大。如果第i个元素前所有的子序列中元素都比它自身大，则说明此时的元素不能与之前的元素构成上升子序列，那么此时dp[i]的值就为1

代码：

#includeusing namespace std;
int a[5000], ans[5000], n;
int main(){cin >>n;
    for(int i = 0; i< n; i++){cin >>a[i];
    }
    ans[0] = 1;
    for(int i = 1; i< n; i++){int maxx = 0;
        for(int j = 0; j< i; j++){if(a[j]< a[i]) maxx = max(maxx, ans[j]);
        }
        ans[i] = maxx + 1;
    }
    sort(ans, ans + n);
    cout<< ans[n - 1];
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧