Giả sử chúng ta có một chuỗi S với n ký tự. Các ký tự sẽ là '+' hoặc '-'. Có một đống đá, n lần chúng tôi lấy một viên đá từ đống đó hoặc thêm một viên đá vào đống. Cọc không trống trước mỗi thao tác lấy một viên đá từ cọc. Chúng ta phải tìm ra số lượng đá tối thiểu có thể có trong đống sau khi thực hiện các thao tác này. Nếu chúng ta lấy viên đá trong phép toán thứ i, S [i] bằng "-", nếu thêm vào, S [i] bằng "+".
Vì vậy, nếu đầu vào là S ="++ - ++", thì đầu ra sẽ là 3. Nếu lúc đầu chúng ta có 0 viên đá trong đống, sau khi thực hiện các phép toán, số viên đá sẽ bằng 3.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
n := size of S for initialize i := 0, when i < n, update (increase i by 1), do: res := (if S[i] is same as '-', then maximum of res - 1 and 0, otherwise res + 1) return res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int n = S.size(), res = 0;
for (int i = 0; i < n; i++)
res = (S[i] == '-') ? max(res - 1, 0) : res + 1;
return res;
}
int main(){
string S = "++-++";
cout << solve(S) << endl;
} Đầu vào
"++-++"
Đầu ra
3