题解 | #牛妹的项链#

思路：

题目的主要信息：

• 用数组a表示项链的不同颜色，即不同数字表示不同颜色，且首尾相接
• 从数组中取出一段数字都不同的连续子序列，求子序列最长长度，需要注意首尾相接的情况

方法一：动态规划
具体做法：
我们可以将数组首尾相接，组成一个的新数组，就不需要再处理循环了。我们用表示以第个珠子结尾的最长连续不相同颜色的长度，遍历新数组，每次判断判断前个珠子是否和第个珠子同色,同色则停下，然后记录下最长长度。

class Solution {
public:
    int solve(int n, vector<int>& a) {
        int res = 0;
        for(int i = 0; i < n; i++) //首尾相接
            a.push_back(a[i]);
        vector<int> dp(2 * n + 1, 0);//dp[i]表示以第i个珠子结尾的最长连续不相同颜色的长度
        dp[1] = 1;
        for(int i = 2; i <= 2 * n; i++){
            int j;
            // 判断前i-1个珠子是否和第i个珠子同色,同色则停下
            for(j = i - 1; j > i - 1 - dp[i - 1] && a[j - 1] != a[i - 1]; j--);
            dp[i] = i - j; //以第i个珠子结尾的最长连续不相同颜色的长度
            res = max(res, dp[i]);  
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，两层循环，每层都是
• 空间复杂度：，辅助数组dp的长度

方法二：哈希表
具体做法：
因为子序列中元素有互异性，我们可以想到用哈希表来查重。因为数组首尾相接是循环，我们可以考虑遍历长度为2倍数组长度，然后取模。遍历的时候，如果遇到一个数字在哈希表中出现过，我们可以比较它最后出现的位置，将现在的位置减去最后出现的作为一次连续子序列的长度，不断维护最大值。同时，每次遇到一个元素之后，需要用哈希表记录其最后一次出现的位置。

class Solution {
public:
    int solve(int n, vector<int>& a) {
        unordered_map<int, int> mp;
        int res = 0;
        int last = 0; //最长子序列的起始位置
        for(int i = 0; i < 2 * n; i++){
            if(mp.find(a[i % n]) != mp.end()){
                last = max(last, mp[a[i % n]]); //找到它最后出现的位置
                res = max(res, i - last); //维护最大值
            }
            mp[a[i % n]] = i;  //记录每个值最后出现的位置
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，一次遍历，循环长度为
• 空间复杂度：，最坏情况下所有元素都不同，哈希表最大