Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string.h>
- #include<map>
- using namespace std;
- string s;
- map<char, map<int, bool>> viz;
- map<char, map<int, int>> dp;
- int solve(char last, int i){
- if(i >= s.size()) return 0;
- if(viz[last][i]) return dp[last][i];
- int L = 0;
- if(last <= s[i]) L = 1 + solve(s[i], i+1);
- int R = solve(last, i+1);
- viz[last][i] = true;
- return dp[last][i] = max(L, R);
- }
- int main(){
- cin >> s;
- cout << solve('A',0) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement