(MAP/递推)Consecutive Subsequence 977-F

题意:找出最长上升连续子序列(5,6,7,8...)
题解:直接用一个map映射每一个的值,递推计算出以每个值为结尾的序列长度,另外有很多map是未初始化的,大概在cf上都默认为0;
一开始用了O(n^2)的LIS改了条件保存路径输出,TLE了,后来用了排序递推,WA了

#include <bits/stdc++.h>
using namespace std;
int arr[200100],N,r,k,last,t,i;
map<int,int> m;
int main(){
    for(cin>>N; i<N ; i++){cin>>arr[i];
        r=m[arr[i]]=m[arr[i]-1]+1;//r=该值=上值-1 
        if(r>k) k=r, last=arr[i];//最大值为下标为r,最大值为last 
    }
    for(cout<<k<<endl, t=last-k+1, i=0 ; i<N ; i++)  //分别找到last-k+1~last的一个下标 
        if(arr[i]==t) cout<<i+1<<" ", t++;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言: 详细介绍: List:元素有放入顺序,元素可重复Map:元素按键值对存储,无放入顺序Set:元素无放入顺序...
    YBshone阅读 8,759评论 0 17
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,099评论 19 139
  • 9月19日国家统计局公布的8月份70个大中城市住宅销售价格变动情况显示,环比价格变动中,郑州涨幅居全国第一:5.6...
    牛奶tiger阅读 675评论 0 0
  • 一、和妈妈一起做咸鸭蛋 早晨起来,妈妈说要做咸鸭蛋。 还是很小的时候,在外婆家,我和妹妹就特别喜欢吃咸鸭蛋。我们俩...
    自乐自鱼阅读 876评论 0 5
  • 1.理清文章各章节脉络和逻辑; 2.带走文章的亮点; 3.含大量自己的感想、心得; 4.与读过的书、已有的知识建立...
    王新印阅读 1,951评论 0 0