すべての操作の後に最小の石を見つけるためのC++コード

n文字の文字列Sがあるとします。文字は「+」または「-」のいずれかになります。石の山があります。n回、山から1つの石を取り出すか、山に1つの石を追加しました。パイルから1つの石を取り出す各操作の前に、パイルは空ではありませんでした。これらの操作を行った後、山に入る可能性のある石の最小数を見つける必要があります。 i番目の操作で石を取った場合、S [i]は「-」に等しく、追加された場合、S[i]は「+」に等しくなります。

したがって、入力がS ="++-++"の場合、出力は3になります。最初に山に0個の石があった場合、操作を行った後、石の数は3に等しくなります。

ステップ

これを解決するには、次の手順に従います-

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

例

理解を深めるために、次の実装を見てみましょう-

#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;
}

入力

"++-++"

出力

3