无锡网站建设品牌大全,网页搜索多个关键词,wordpress主题哪里买,中国移动网站官网最长上升子序列2
时间限制#xff1a;1秒 内存限制#xff1a;64M
题目描述
给定一个长度为 N 的数列#xff0c;求数值严格单调递增的子序列的长度最长是多少。
输入描述
第一行包含整数 N。
第二行包含 N 个整数#xff0c;表示完整序列。
输出描述
输出一…最长上升子序列2
时间限制1秒 内存限制64M
题目描述
给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。
输入描述
第一行包含整数 N。
第二行包含 N 个整数表示完整序列。
输出描述
输出一个整数表示最大长度。
样例
输入
7
3 1 2 1 8 5 6
输出
4
提示
N1e5
−10^9≤数列中的数≤10^9
#includeiostream
#includealgorithm
using namespace std;
const int N1e52;
long long a[N],sum[N],ans;
int main() {int n;cinn;for(int i1;in;i){cina[i];}ans1;sum[ans]a[1];for(int i2;in;i){if(a[i]sum[ans]){ans;sum[ans]a[i];}else{int xlower_bound(sum1,sumans1,a[i])-sum;sum[x]a[i];}} coutansendl;return 0;}
解题步骤
首先我们需要读取输入的序列长度和序列本身。然后我们可以使用动态规划的方法来求解最长单调递增子序列的长度。我们可以定义一个数组dp其中dp[i]表示以第i个元素结尾的最长单调递增子序列的长度。状态转移方程为dp[i] max(dp[j]) 1其中0 j i且nums[j] nums[i]。最后我们输出dp数组中的最大值即为最长单调递增子序列的长度。
