最长非重复子序列

使用双指针算法解决这个问题。 这其中的核心问题是如何记录已经访问的元素和失配(miss match)后的的算法行为。

#include <iostream>
using namespace std;

const int N = 100010;
int a[N] , s[200];

// 用s数组纪录元素出现的个数 s的长度只需覆盖ascii码的范围即可
// 每当i前进 就会多记录一个元素 那么和可能重复的元素就是a[i]
// 当重复发生时 (s[a[j]] > 1) 为了消除这种重复 要向前移动j 直到a[i]重新为1
// 每当i增加 记录当前的最大长度

void Longest_NonRepeating_Subsequence()
{
    int n , maxL = 0;
    cin >> n;
    // 将字符串读入数组
    for(int i = 0 ; i < n ; i++) cin >> a[i];

    // 遍历这个串
    for(int i = 0 , j = 0; i < n ; i++)
    {
        s[a[i]]++; // 将这个遇到的元素 计数加一
        while(s[a[i]] > 1) // 如果当前元素的计数大于一 那么不断减少区间的左部分
        {
            s[a[j]]--;
            j++;
        }
        maxL = max(maxL , i - j + 1); // 记录当前区间的长度
    }
    cout << maxL << endl;

}