UVa 11572 Unique Snowflakes
💡
原文中文，约1500字，阅读约需4分钟。
📝
内容提要
题目要求找出给定数列中不含重复数字的最长子序列长度。通过记录每个数字第一次出现的位置，利用两个指针更新子序列的起点和长度，最终输出最长子序列的长度。
🎯
关键要点
- 题目要求找出给定数列中不含重复数字的最长子序列长度。
- 使用数组pos记录每个数字第一次出现的位置，初始化为-1。
- 通过两个指针更新子序列的起点和长度。
- 当枚举到i时，如果pos[arr[i]]<start，说明该数字在当前子序列中出现过，停止本次枚举。
- 如果pos[arr[i]]>start，则长度加1，继续枚举，直到结束。
- 最终输出的长度是最长子序列的长度。
❓
延伸问答
如何找到不含重复数字的最长子序列的长度？
通过记录每个数字第一次出现的位置，并使用两个指针更新子序列的起点和长度来找到最长子序列的长度。
在这个算法中，如何记录数字第一次出现的位置？
使用一个数组pos来记录每个数字第一次出现的位置，初始化为-1。
当遇到重复数字时，算法如何处理？
如果当前数字在子序列中出现过，则停止本次枚举，并更新子序列的起点。
这个算法的时间复杂度是多少？
算法的时间复杂度为O(n)，因为每个数字只被处理一次。
如何初始化数组pos？
数组pos在开始时被初始化为-1，以表示数字尚未出现。
最终输出的结果是什么？
最终输出的是不含重复数字的最长子序列的长度。
➡️
