最大连续子序列-白红宇的个人博客

最大连续子序列

发布日期：2021-06-30 15:15:55 浏览次数：3 分类：技术文章

本文共 1688 字，大约阅读时间需要 5 分钟。

周六早上做了一道A题，按道理讲应该难度不大，但涉及到一个基本的知识点是求最大连续子序列，其实这个东西我不怎么熟悉，在网上看到了别人的相关代码，顺利AC。

codeforces题目链接在这里：

最大连续子序列相关资料却是别人整理的leetcode：

codeforces中这个题目本质上就是求最大连续子序列，下面内容是第二个链接中对最大连续子序列这类题目的分析，工具为哈希表。

哈希表插入和查找一个数的时间是O（1），因此可以使用哈希表来保存数组，以保障数组中的元素查找是常量时间；一个数和它相邻的数都在同一个连续子序列中，因此，在某个数开始进行最长连续子序列判断的时候，可以将与它在同一个连续子序列中的元素标记为不作为判断的开始，因为该元素锁在的连续子序列处理过了，从而减少比较次数，降低计算复杂度。

由于C++实现中的哈希表是一个无序字典类型，因此，可以将数组元素作为关键字，每一个元素标记位作为每一个关键字的值。

对于数组中的每一个元素，先判断其所在的连续子序列是否处理过了，如果处理过了，则直接处理下一个元素；如果没处理过，则以其为中心，向左向右查找是否有相邻数存在于数组中，如果存在就将长度加1，并将该元素的标记位置位，表示该元素所在的连续子序列处理过了，一直查找下去，直到相邻的数字不存在数组中为止，记录序列的长度，然后处理下一个元素。按照这个方法，在进行最长连续子序列查找的过程中，每个元素只被访问过一次，因此计算复杂度为O(n)。

在创建哈希表的过程中，计算复杂度也为O(n），因此整个算法的时间复杂度就是O(n)。

最后贴一下这个题目的代码，当然可能存在更简单的解决办法，毕竟这只是一道A题

#include
   
    #include
    
     #include
     
      #include
      
       #include
       using namespace std;vector
        
          v;int n, d;string s;int judge(string s){ for (int i = 0; i < s.size(); ++i) if (s[i] == '0') return 1; return 0;}int main(){ cin >> n >> d; for (int i = 1; i <= d; ++i) { cin >> s; if (judge(s)) v.push_back(i); } int sz = v.size(), res = 0; map
         
           HashTable; //build the hash table for (int i = 0; i < sz; ++i) HashTable[v[i]] = false; //find the longest consecutive sequence int LongestNum = 0; for (int i = 0; i < sz; ++i) { int tmp = v[i];//先向右查找 if (HashTable[tmp]) continue; int tmpsequence = 1; //map对象的find函数返回一个迭代器指向键值为key的元素 //如果没有找到就返回指向map尾部的迭代器 while (HashTable.find(++tmp) != HashTable.end()) { HashTable[tmp] = true; tmpsequence++; } tmp = v[i];//再向左查找 while (HashTable.find(--tmp) != HashTable.end()) { HashTable[tmp] = true; tmpsequence++; } LongestNum = max(LongestNum, tmpsequence); } cout << LongestNum << endl; return 0;}

转载地址：https://jianzhuwang.blog.csdn.net/article/details/51810032 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：what are textons?

下一篇：Fast Randomized SVD

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章