在数组A[0…n]中求一个子数组A[i…j]，使得这个数组里的所有元素都不重复。那么这个子数组，长度最大为多少？
比如：
{1, 2, 3} → 3
{1} → 1
{1, 2, 3, 2, 1} → 3
直观的来看，如果采用暴力搜索。
令OPT(i) = 以A[i]为结尾的最大不重复子数组;
那么原问题的答案 = max{OPT(0) ,OPT(1) … OPT(n)}
如果给定了A[i]，求以A[i]为结尾的最大不重复子数组，那么可以往前遍历，把所有遇到的元素，都加在一个set里，直到发现有重复的就停下来。于是这个问题在O(N)的时间内解决。
于是总体来说，通过两层循环，就可以在O(N*N)的时间内解决。
但是实际上这个问题有O(N)的办法，因为OPT(i) 可以在O(1)的时间内解决。
此时我们需要维护一个head标记，每次循环的时候更新head的值让[head…i]之间的所有元素都是不重复的。
于是，head指针的初始值是0，每遇到一个重复的元素，假设这个元素上一次出现的位置是p，那么head=max(head,p+1)。
那么怎么知道这个元素上次出现的位置在哪呢？ 用MAP吧。
拿{1, 2, 3, 2, 1} 为例来说，当扫描到第4个元素a[3]==2时
last[1] == 0
last[2] == 1
last[3] == 2
head本来等于0。此时要更新成1。于是以a[3]为结尾的最大不重复子数组的长度就是3-1=2。具体实现代码如下
template
struct mdsfunc{
//value是key上次在数组中出现的位置（index,从0开始编号)
typedef typename std::unordered_map<T,size_t> MAP_TYPE;
MAP_TYPE all;
//all当中second的最小值+1
//如果all.empty()，start=0;
size_t start;
mdsfunc():start(0){}
//a[index]=n
size_t operator()(const T& n,size_t index){
typename MAP_TYPE::iterator iter=all.find(n);
if(iter==all.end()){
//n没有出现过
all[n]=index;
} else{
start=std::max(start,iter->second+1);
iter->second=index;
}
return index-start+1;
}
};
/**
- 在[begin,end)中间求子区间0<=s<=t<end使得[s…t]中的每个元素都各不相同
- 求满足上述条件的长度最大的
- 题目参考：http://uva.onlinejudge.org/external/115/11572.html
- \return 子区间的长度
*/
template
size_t maxDistinctSubArrayLen(Iterator begin,Iterator end){
size_t maxlen(1);
size_t index=0;
typedef typename std::iterator_traits::value_type ValueType;
mdsfunc f;
for(Iterator iter=begin;iter!=end;++iter){
maxlen=std::max(maxlen,f(*iter,index++));
}
return maxlen;
}