codeforce每日一题链接
题目描述
给你一个字符串,每个字符不是$’<’$,就是$’>’$。有一个数组$a$,$s[i]$为$’<’$表示a[i] < a[i+1],$s[i]$为$’>’$表示$a[i]>a[i+1]$,请返回$a$的最小代价。数组的代价是数组中不同元素的数量。
样例
输入样例1
4
4
<<>>
4
>><<
5
>>>>>
7
<><><><
输出样例1
3
3
6
2
算法
(暴力枚举) $O(n)$
找出最大连续的’<’或者’>’的长度,答案就是最大长度加1。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n;
string str;
cin>>str;
int res = 0;
for(int i=0;i<n;i++){
int j = i;
while(j<n && str[j]==str[i]) j++;
res = max(res, j - i);
i = j - 1;
}
cout<<res + 1<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}