Tìm số đá tối thiểu sau các phép toán bằng C++

Mô tả bài toán

Cho chuỗi S chỉ chứa '+' và '-'. Bắt đầu với 0 đá. '+' thêm 1 đá, '-' lấy 1 đá (chỉ lấy khi đống không rỗng). Tìm số đá tối thiểu có thể có sau n phép toán.

Ví dụ

S = "++-++" → Output: 3. Nếu bắt đầu 0: + + - + + → 1,2,1,2,3.

Thuật toán

Mô phỏng: res=0. Duyệt S: nếu '+' thì res++; nếu '-' thì res = max(res-1, 0). Trả về res.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
    int res = 0;
    for (char c : S) {
        if (c == '-') res = max(res - 1, 0);
        else res++;
    }
    return res;
}

int main() {
    string S = "++-++";
    cout << solve(S) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: "++-++"

Output: 3