# my C++ code using dynamic programming

• There are two basic cases for starting DP.
When length is odd, for example "xax",
and when length is even, for example "xaax".

``````bool D[1001][1001];

class Solution {
public:
string longestPalindrome(string s) {
int len = s.length();
/* base case */
for(int i=0; i<len; i++){
for(int j=0;j<len;j++)
D[i][j] = false;
D[i][i] = true;
}

int max = 1;
int start = 0;
int end = 0;

/* base case for even length */
for(int i=0; i<len; i++){
if(i+1 < len){
D[i][i+1] = s.at(i) == s.at(i+1) ? true: false;
if(D[i][i+1]){
max = 2;
start = i;
end = i+1;
}
}
}

int s_i, e_i;
for(int i=0; i< len; i++){
/* odd */
s_i=i-1;
e_i=i+1;
while(s_i>=0 && e_i<=len-1){
if(D[(s_i+1)][e_i-1] && (s.at(s_i) == s.at(e_i))){
D[s_i][e_i] = true;
/* update max */
if((e_i-s_i+1) > max){
max = e_i-s_i+1;
start = s_i;
end = e_i;
}
}
s_i--;
e_i++;
}
/* even */
s_i=i-1;
e_i=i+2;
while(s_i>=0 && e_i<=len-1){
if(D[(s_i+1)][e_i-1] && (s.at(s_i) == s.at(e_i))){
D[s_i][e_i] = true;
/* update max */
if((e_i-s_i+1) > max){
max = e_i-s_i+1;
start = s_i;
end = e_i;
}
}
s_i--;
e_i++;
}
}

return s.substr(start, max);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.