深圳营销型网站建设-龙华信科,工程建设是干什么的,网站前端跟后端怎么做,长春的seo服务公司C 求最长似递增子序列 是子序列#xff01; 我误以为是最长上升子序列的变式#xff0c;但是这个题目和那个题目#xff0c;并不是很一样
我们选择观察样例#xff1a; 1 2 4 3 3 5 6 2 1
其实样例当中就给我们了答案#xff0c;我们能感觉的出来#xff0c;应该是用长…C 求最长似递增子序列 是子序列 我误以为是最长上升子序列的变式但是这个题目和那个题目并不是很一样
我们选择观察样例 1 2 4 3 3 5 6 2 1
其实样例当中就给我们了答案我们能感觉的出来应该是用长度去减去一个东西但是应该减去一个什么东西呢【46】之间这个是3虽然说第二个三看起来在序列当中是一个不合格的元素但是实际上在这里是一个合格的元素对于我们选定的区间而言我们其实是没有必要去追求前两个的前两个一定是符合要求的所以我们需要看的是在我们选定的区间抛出前两个元素之后剩下的元素当中不符和要求的最长的子序列此处是一个子序列
#include iostream
using namespace std;
const int N 200000 10;
int a[N];
int s[N];
int main(){int n;int k;cin n k;for(int i 1;i n;i ) cin a[i];for(int i 3;i n;i ){if(a[i] a[i - 1] a[i - 1] a[i - 2]){s[i] 1;}}for(int i 1;i n;i ) s[i] s[i - 1];while(k --){int l,r;cin l r;if(r - l 1 2) cout r - l 1 endl;else cout (r - l 1) - s[r] s[l 1] endl;}return 0;
}
