算法設(shè)計與優(yōu)化策略——滑動窗口

“滑動窗口”和上篇博客中介紹的“等價轉(zhuǎn)換”一樣也為一種算法優(yōu)化的思想。同樣，下面通過一個例子，來介紹這種思想。
唯一的雪花（Unique snowflake，UVa 11572）
輸入一個長度為n(n<=10^6)的序列A，找到一個盡量長的連續(xù)子序列AL~AR,使得該序列中沒有相同的元素。
在讀完題目以后，我們不難有思路。最簡單的思路就是，我們可以通過循環(huán)的方法，對每一個元素都找出一它為開頭的最長序列（沒有相同元素）。這個方法也能做出來，但似乎有點(diǎn)太麻煩了。下面，我們就通過“滑動窗口”的思想來介紹這道題目的另一個思路。
【分析】
假設(shè)序列元素從0開始編號，所求連續(xù)子序列的左端點(diǎn)為L,又短點(diǎn)為R。首先，先考慮L=0的情況?？梢詮腞=0不斷增加R，相當(dāng)于，把所求序列的右端點(diǎn)往右延伸。當(dāng)R不能往右繼續(xù)延伸時（即出現(xiàn)相同的元素時），只需將L不斷增加至沒有相同的元素時為止。然后再不斷增加R，重復(fù)此步驟。
【代碼】通過代碼來實(shí)現(xiàn)上述過程，加深理解

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1000000+5;
int A[maxn];
int main()
{
        int T,n;
        scanf("%d",&T);
        while(T--){
                scanf("%d",&n);
                for(int i=0;i<n;i++) scanf("%d",&A[i]);
                set<int> s;
                int L=0,R=0,ans=0;
                while(R<n){
                        while(R<n&&!s.count(A[R])) s.insert(A[R++]);
                        ans=max(ans,R-L);
                        s.erase(A[L++]);
                        }
                        printf("%d\n",ans);
                }
                return 0;
    }

同時，此題用C++的STL中的set，實(shí)現(xiàn)了這一過程。