You are viewing a single comment's thread. Return to all comments →
Slight rough code but it works for longest pallindromic subsequence
int call(string& s, vector<vector<int>>& dp, int start, int end) { if(start > end) return 0; if(dp[start][end] != -1) return dp[start][end]; int res = 0; if(s[start] == s[end]) { int curr = 2; if(start == end) curr = 1; res = max(res,curr + call(s, dp, start+1, end-1)); } else { res = max(res, call(s, dp, start+1, end)); res = max(res, call(s, dp, start, end-1)); // res = max(res, call(s, dp, start+1, end-1)); } return dp[start][end] = res; } int playWithWords(string s) { int n = s.size(); int ans = 0; vector<vector<int>> dp(n+1, vector<int>(n+1, -1)); for( int i = 0 ; i < n ; ++i ){ ans = max( ans , call( s, dp, 0, i) * call(s, dp, i + 1 , n-1) ); } return ans; }
Seems like cookies are disabled on this browser, please enable them to open this website
Play with words
You are viewing a single comment's thread. Return to all comments →
Slight rough code but it works for longest pallindromic subsequence