牛妹的项链

最优题解

因为是一个环，所以可以把整个数组复制一份加在后面来为每个位置选择最优决策点。
问题等价于求：选取最长的一段没有重复的数字
定义dp(i)的含义：设截取的段以第个珠子为右端点的话，它的左端点至少要大于
对于位置i的珠子，这个位置要么单独一个珠子作为一段，要么会和第个珠子连在一起，所以
同时要保证这个颜色的珠子是唯一的，所以要记录每个颜色最后一次出现的位置last[x]，
所以
在dp的过程中记录答案即可。
需要map存放每个数字最后一次出现的位置，空间复杂度
时间复杂度取决于如何记录每个数字最后一次出现位置，使用map存则每次查询时间复杂度,总的时间复杂度。若是使用unordered_map或是哈希表则可能做到查询，但是也有退化为的风险。

int dp[200005];
int solve(int n,vector<int> &a){
    assert(a.size() == n);
    for(int i = 0; i < n; ++i) a.push_back(a[i]);
    map<int,int> last; last.clear();
    int ans = 1;
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= 2*n; ++i){
        int x = a[i-1];
        if(last.find(x) == last.end()){//x第一次出现
            dp[i] = dp[i-1];
        }else{
            dp[i] = max(dp[i-1], last[x]);
        }
        ans = max(ans, i-dp[i]); last[x] = i;
    }return ans;
}