We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Struggled a bit on this but wound up with modified code for longest palindromic subsequence:
defplayWithWords(s):n=len(s)dp=[[0for_inrange(n)]for_inrange(n)]# Every individual char is a palindrome of 1foriinrange(n):dp[i][i]=1# Get longest palindromic subsequencesforstartinrange(n-1,-1,-1):forendinrange(start+1,n):ifs[start]==s[end]:dp[start][end]=2+dp[start+1][end-1]else:dp[start][end]=max(dp[start+1][end],dp[start][end-1])# Get max product from DP table by calculating non-overlappingmax_prod=0forsub1_endinrange(n-1):sub2_start=sub1_end+1max_prod=max(max_prod,dp[0][sub1_end]*dp[sub2_start][n-1])returnmax_prod
Play with words
You are viewing a single comment's thread. Return to all comments →
Struggled a bit on this but wound up with modified code for longest palindromic subsequence: