รหัส C ++ เพื่อค้นหาหินขั้นต่ำหลังจากการดำเนินการทั้งหมด

สมมติว่าเรามีสตริง S ที่มีอักขระ n ตัว อักขระจะเป็น '+' หรือ '-' มีกองหิน n ครั้งที่เราเอาหินหนึ่งก้อนจากกองหรือเพิ่มหินหนึ่งก้อนลงในกอง กองไม่ว่างก่อนการดำเนินการแต่ละครั้งจะนำหินหนึ่งก้อนออกจากกอง เราต้องหาหินให้น้อยที่สุดเท่าที่จะเป็นไปได้ในกองหลังจากดำเนินการเหล่านี้ ถ้าเราเอาหินไปปฏิบัติครั้งที่ 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;
}

อินพุต

"++-++"