Desafío Dal Lago #1 : String bien parenteseado

Problemas
#1

He aquí la primera de las que espero sean muchas ediciones de los “Desafíos Dal Lago”. La intención es proponer problemas para la comunidad, incentivando el uso del foro y la discusión de participantes de todos los niveles. Los problemas pueden ser conocidos, super clásicos, o podrían ser totalmente nuevos.

Problema: Dado un String bien parenteseado1 dar la máxima profundidad de paréntesis. La profundidad de paréntesis la definimos como la cantidad de paréntesis que llevo sin cerrar en un determinado momento. Intuitivamente es que tan anidados están los paréntesis.
Ejemplo:

  1. () Rta: 1. Abrimos un solo paréntesis.
  2. ()() Rta: 1. Luego de abrir cada parentésis, lo cerramos.
  3. (()) Rta: 2. Abrimos un paréntesis anidado.
  4. (()()(())) Rta: 3. El último paréntesis que se abre tiene profundidad 3.

Entrada: Un String que consiste exclusivamente de caracteres ‘(’ y ‘)’.
Salida: Máxima profundidad de paréntesis.

Referencias:

  1. Un String bien parenteseado es un String donde no cerramos paréntesis de más o de menos.
    Ejemplos son los que están arriba para entradas del problema.
    Algunos Strings MAL parenteseados: “())”, “(()”, “)”.

Comentarios:
Este problema se le ocurrió a Román Castellarin.

4 Me gusta
#2

Hola.
Dejo mi solución al problema.

Código 
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for(int i=s;i<n;i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()

typedef long long tint;

int main() {
	string s; cin >> s;
	int n = s.size();
	int cont = 0;
	int maxiSize = 0;
	forn(i, n){
		if(s[i] == '(') cont++;
		else cont--;
		maxiSize = max(maxiSize, cont);
	}
	cout << maxiSize << "\n";
}
1 me gusta