题解 | #C++实现数组中的最长连续子序列#

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

//重点是当前序列的最小值和最大值以及当前序列的长度
//一旦序列长度发生改变，只需要更改最大值和最小值对应的value
//最终返回当前序列的长度
//最终求得最长的序列长度

int merge(map<int, int> &mp, int less, int more)
{
    int left = less - mp[less] + 1;//当前序列中最小的数据
    int right = more + mp[more] - 1;//当前序列中最大的数据
    int len = right - left + 1;//当前序列的长度
    mp[left] = len;//在最小值上更新当前序列的长度
    mp[right] = len;//在最大值上更新当前序列的长度
    return len;//返回当前的序列长度
}
int main()
{
    int num;
    while (cin >> num)
    {
        int ret = 1;
        vector<int>arr;
        //接收数据
        for (int i = 0; i < num; i++)
        {
            int n;
            cin >> n;
            arr.push_back(n);
        }
        //创建map
        map<int, int> mp;
        for (int i = 0; i < num; i++)
        {
            if (mp.find(arr[i]) == mp.end())
            {
                //插入未出现的数据
                mp.insert({ arr[i],1 });
                //如果有比当前数据小1的数据已经存在，则把当前数据连接到已有序列最后
                if (mp.find(arr[i] - 1) != mp.end())
                {
                    ret = max(ret,merge(mp,arr[i]-1,arr[i]));
                }
                //如果有比当前数据大1的数据已经存在，则把当前数据连接到已有序列最前方
                if (mp.find(arr[i] + 1) != mp.end())
                {
                    ret = max(ret, merge(mp, arr[i], arr[i]+1));
                }
            }
            else
                continue;
        }
        cout << ret << endl;
    }
    return 0;
}