牛妹的项链

class Solution:
    def solve(self, n, a):
        dp = [0] * n  # 记录每个位置的最大值
        dp[0] = 1  # 第一个位置初始值为1
        ind = 0  # 记录没有颜色重复的初始位置，初始值为0
        for i in range(1, n):  # 从第二个位置开始更新dp
            if a[i] in a[ind:i]:  # 第i个颜色是否为重复颜色
                c = a[ind:i]  # 将没有颜色重复的这一段截取出来
                c.reverse()  # 反转，为了下一步得到和第i个颜色重复的珠子的位置
                ind += (len(c) - 1) - c.index(a[i])  
                # ind加上 和第i个颜色重复的珠子在没有颜色重复区间的位置，得到和第i个颜色重复的珠子在整串珠子中的位置
                dp[i] = i - ind  # 得到dp[i]
                ind += 1  # 更新没有颜色重复的初始位置
            else:  # 第i个颜色没有重复时
                dp[i] = i + 1 - ind  
                
        # 考虑将首位两端连接的情况
        aa = a[-dp[-1]:]  # 截取最后一个位置能得到的最大长度，在考虑从第一个开始往后的颜色有无重复即可
        j = 0
        while a[j] not in aa:  # 没有重复，将dp[i]加一即可，有重复就停止
            dp[-1] += 1
            j += 1
        return max(dp)  # 返回dp[i]的最大值，即最大的长度

int solve(int n, vector<int>& a) {
        // write code here
        vector<int> dp(n+1, 0); // dp[i]表示以第i个珠子结尾的最长单色长度
         
        dp[1]=1;
        int res=0;
        for(int i=2;i<=n;i++){ // 单向遍历搜索，以i结尾的最长长度
            int pre=i-1;
            for(; pre>i-1-dp[i-1] && a[pre-1]!=a[i-1];pre--){ // 判断前dp[i-1]个珠子是否和第i个珠子同色， 同色就停下
            }
            dp[i]=i-pre; // 第i个珠子结尾的最长长度
            res=max(res, dp[i]);
        }
         
        int i=1;
        // 还没有判断首尾相连的情况，所以遍历首部的几个珠子。
        // 符合条件的是，前i个珠子都不同色（若存在同色，则不用继续向后了），并且不在尾部的那个序列中
        for(;i>=dp[i] && i<n-dp[n];i++){ 
            int j=n;
            for(;j>n-dp[n] && a[i-1]!=a[j-1];j--){ // 判断第i个珠子是否和尾部的珠子同色
            }
            if(j>n-dp[n]){
                i++;
                break;
            }
        }
        res=max(res, dp[n]+i-1); // i是首部符合条件的后一个，所以减1
         
        return res;
    }