题意简述
给定一个整数序列 $a_1, a_2, \dots, a_n$。设 $S$ 是所有不含重复元素的非空子序列的集合。你的目标是找到 $S$ 中长度最长的子序列。
如果有多个这样的序列，找到其中经过将奇数位置的元素乘以 $-1$ 后字典序最小的那个。
思路分析
使用贪心策略。
首先，最长的子序列必然由原序列中所有不同的元素组成，其长度为原序列中不同元素的数量。
为了满足题意的要求，需要使奇数位置的元素尽可能大，偶数位置的元素尽可能小，并且越靠前越优。
具体做法如下：
- 跳过已占据合适位置的元素：如果当前元素已经在前面的位置找到了合适的安排，那么直接跳过。因为继续使用当前元素不会得到比已有更优的结果。
- 为当前元素找到合适位置：如果当前元素还没有在子序列中出现，那么就需要考虑将它加入子序列。具体做法是从已经构造好的子序列末尾开始，比较当前元素与末尾元素：
- 如果当前元素比末尾元素更适合填在该位置，并且末尾元素在后续还有出现的机会，则将末尾元素移除，并继续检查当前元素是否可以放置在更靠前的位置。
- 如果当前元素更适合出现在倒数第二个位置，则移除子序列末尾的两个元素，继续重复上述步骤，直到找到适合放置当前元素的位置为止。
找到合适位置后，将当前元素放入子序列末尾。
通过上述贪心策略，可以构造出满足条件的最长子序列，并且字典序最小。