本题是要在序列中寻找一个区间,区间内元素不重复,且长度为全局最长。❄

结合线性动规思想,$dp_i$记录以每一项为终点的最长区间的起始位置。因此,每一项元素要通过结构体记录雪花的类别,以及该类别。在此之前最后出现的位置。遍历每一项,通过哈希表的构建查询当前项类别的雪花是否存在,无则插入,有则相应修改该类别的末尾位置信息,通过末尾信息逐项更新$dp_i$的值,求出区间长度,全局判断求最大值。

动规:

• 定义状态变量：$dp[i]$表示以i结尾符合条件的区间头

• 状态转移方程： 我们定义$x$为当前雪花,因为只需查询$[dp[i],i]$区间内是否有元素与$x$重复 所以,当区间内有元素与$x$相同时,$dp[i] = find(x, i) + 1$,否则为$dp[i] = dp[i - 1]$

  也就是$dp[i] = max(dp[i - 1],find(x, i) + 1)$。

哈希表:

哈希表可以用更少的时间和空间来查找元素,在此以vector动态数组来实现。又因为是结合动规来实现,查找时需要返回下标,所以用结构体存。

struct node
{
	int x, k;  //x为节点值,k为动规循环下标
};
vector <node> h[1000001];

插入函数:

void insert(int x,int i)
{
	h[x % mod].push_back((node){x,i});
}

查询函数(注意返回值):

int find(int x,int i)
{
	int k = 0;
	for(int j = 0;j < h[x % mod].size();j++)
	{
		if(h[x % mod][j].x == x)
		{
			k = h[x % mod][j].k;//取下标
			h[x % mod][j].k = i;//更改下标为当前循环i
			break;
		}
	}
	return k;
}

代码:

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x,k;
};
const int mod = 100007;
int n,x,k,dp[1000007],ans;
vector <node> h[1000007];

void insert(int x,int i)
{
	h[x % mod].push_back((node){x,i});
}

int find(int x,int i)
{
	int k = 0;
	for(int j = 0;j < h[x % mod].size();j++)
	{
		if(h[x % mod][j].x == x)
		{
			k = h[x % mod][j].k;
			h[x % mod][j].k = i;
			break;
		}
	}
	return k;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> x;
		k = find(x,i);
		dp[i] = max(dp[i - 1],k + 1);
		ans = max(ans,i - dp[i] + 1);
		insert(x,i);
	}
	cout << ans;
	return 0;
}