原题链接：https://codeforces.com/contest/1304/problem/D
题目描述
Gildong最近研究了LIS（Longest Increasing Subsequence，最大上升子序列，参考链接）的问题。
现在，Gildong想出了这样一个问题：给定一个由 “<” 和 “>” 组成的长度为n-1的字符串，其中，每个符号代表了它两端数字的比较关系，即小于或大于。接下来，需要利用从1到n这n个数字，构造一个长度为n的数字序列 a0a1..an−1，序列中的每个数字各不相同。
比如，当n=4时，给定关系>><，则满足条件的数字序列有3214、4213等。
现在的目标是，在所有满足给定条件的数字序列中找出两个，其中，第1个的LIS尽可能短，第2个的LIS尽可能长。
如果有多个数字序列满足要求，则只输出其中一个即可。
测试数据
输入
第一行是一个数字t，描述测试用例的数量。
接下来t行，每行是一个测试用例。每个用例有两个字段，分别是n和一个包含了 < 和 > 的长度为n-1的字符串
输出
针对每个测试用例，输出两行，第1行是拥有最短LIS的数字序列，第2行是拥有最长LIS的数字序列。
如果有多个数字序列满足要求，则只输出其中一个即可。
例：
# Input
3
3 <<
7 >><>><
5 >>><
# Output
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3
题目解析
仔细分析一下，其实此题只是借用了LIS的定义，与LIS算法本身并无太大关系。
再分析一下，在限定条件中，其实连续的小于号就是一个上升子序列，那么，我们要找的最小LIS长度尽量就是限定条件中连续小于号的长度（最长的连续小于号）。而连续的大于号构成的数字序列内部不可能有上升序列。
综上，现在对限定条件中的符号进行分组，连续的相同符号为一组。以上面第2条用例为例
在求最小LIS时，可以让组1内的数字都大于组2，组2内的数字都大于组3，组3内的数字都大于组4。
求最大LIS时，可以让组1内的数字都小于组2，组2内的数字都小于组3，组3内的数字都小于组4。
在这个思路下，其实可以这样操作：在求最小LIS时，先将1到n这n个数字从大到小排列（相当于都用>连接），然后对照限定条件，将<两端的数字对换，最终得到的就是最小LIS。
在求最大LIS时，先将1到n这n个数字从小到大排列（相当于都用<连接），然后对照限定条件，将>两端的数字对换，最终得到的就是最大LIS。
参考代码
"""
Shortest and Longest LIS
https://codeforces.com/problemset/problem/1304/D
"""
import sys
def reverse_items(seq, reverse_start, reverse_end):
"""
reverse charactors in seq from reverse_start to reverse_end, inclusive
:param seq:
:param reverse_start:
:param reverse_end:
:return:
"""
while reverse_start<reverse_end:
tmp = seq[reverse_start]
seq[reverse_start] = seq[reverse_end]
seq[reverse_end] = tmp
reverse_start += 1
reverse_end -= 1
def output_shortest_and_longest(max_number, comp_serial):
# construct two sequences
increasing_seq = [str(i) for i in range(1, max_number+1)]
decreasing_seq = [s for s in reversed(increasing_seq)]
continuous_lt_start = None
continuous_gt_start = None
last_comp_symbol = comp_serial[0]
for i in range(0, len(comp_serial)):
ch = comp_serial[i]
if ch == '<':
if continuous_lt_start is None:
continuous_lt_start = i
if ch != last_comp_symbol:
reverse_items(increasing_seq, continuous_gt_start, i)
continuous_gt_start = None
else:
if continuous_gt_start is None:
continuous_gt_start = i
if ch != last_comp_symbol:
reverse_items(decreasing_seq, continuous_lt_start, i)
continuous_lt_start = None
last_comp_symbol = ch
if continuous_lt_start is not None and comp_serial[-1]=='<':
reverse_items(decreasing_seq, continuous_lt_start, len(comp_serial))
if continuous_gt_start is not None and comp_serial[-1]=='>':
reverse_items(increasing_seq, continuous_gt_start, len(comp_serial))
print(' '.join(decreasing_seq))
print(' '.join(increasing_seq))
def solve():
left_cases = None
# read file
for line in sys.stdin:
if left_cases is None:
left_cases = int(line.strip())
else:
vals = line.split()
output_shortest_and_longest(int(vals[0]), vals[1])
left_cases -= 1
if left_cases == 0:
break
# Over
if __name__ == '__main__':
solve()