Educational Codeforces Round 149 (Rated for Div. 2) B. Comparison String
给一个长度为 \(n\) 的字符串 \(s\) ，只包含字符“<”、“>”。
一个长度为 \(n + 1\) 的数组 \(a\) 与 \(s\) 是兼容的当且仅当对于任意 \(i\) ：
- \(s_i\) is \(<\) ，当且仅当 \(a_i < a_{i - 1}\)
- \(s_i\) is \(>\) ，当且仅当 \(a_i > a_{i - 1}\)
定义一个数组的 \(cost\) 为这个数组中不同数的个数。
求一个 \(cost\) 最小的且与 \(s\) 匹配的数组，只需要输出 \(cost\) 。
观察一：一个 \(<\) 或 \(>\) 可以作为连接两个节点 \((u, v)\) 的边，且 \(|u - v| = 1\) 。
观察二：整个 \(s\) 由若干段单调的段组成。
观察三：每次单调性发生改变时。如单增改为单减，为保证值域尽可能小，可以将递减的起点设为最高点。另一种情况同理。
观察四：答案为最长单调段长度 \(+ 1\) 。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::string Str; std::cin >> Str;
int ans = 0;
for (int i = 1; i <= n; i++) {
int j = i;
while (j <= n && Str[j - 1] == Str[i - 1]) j++;
j -= 1;
ans = std::max(ans, j - i + 1);
i = j;
}
std::cout << ans + 1 << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}