Maior Palíndromo com Programação Dinâmica

maximum_palindrome.cpp

#include <bits/stdc++.h>

using namespace std;
#define MAX 100

int memo[MAX][MAX];
string word;

//r == right, l == left
int maior_palindromo(int l, int r){
	
	if(l == r)
		return memo[l][r] = 1;
	if(l+1 == r)
		return memo[l][r] = word[l] == word[r] ? 2 : 1;
	if(memo[l][r] != -1)
		return memo[l][r];
	if(word[l] == word[r])
		return memo[l][r] = 2 + maior_palindromo(l+1, r-1);
	return memo[l][r] = max(maior_palindromo(l+1, r), maior_palindromo(l, r-1));
}	

int main(){

	cin>>word;
	  
 	int size_word = (int)word.size();
	for(int x=0; x<size_word; x++)
		for(int y=0; y<size_word; y++)
			memo[x][y] = -1;
		
	cout << maior_palindromo(0, size_word-1) << endl;	
	
	return 0;
}