14453번: Hoof, Paper, Scissors (Silver)

https://www.acmicpc.net/problem/14453


$O(n)$

임의의 경계에 대해 이를 기준으로 왼편과 오른편의 H, P, S만의 최대 개수 합의 최댓값이 답이 된다.

#include<cstdio>
int n, s[3][100001], res;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        char c;
        scanf(" %c", &c);
        for (int j = 0; j < 3; j++) s[j][i] += s[j][i - 1];
        s[(c - 'A') / 8][i]++;
    }
    for (int i = 1; i <= n; i++) {
        int l = 0, r = 0;
        for (int j = 0; j < 3; j++) {
            if (l < s[j][i]) l = s[j][i];
            if (r < s[j][n] - s[j][i]) r = s[j][n] - s[j][i];
        }
        if (res < l + r) res = l + r;
    }
    printf("%d", res);
    return 0;
}