# Why my Dynamic Programming O(n^2) exceeds time limit?

• public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int [][] LPS= new int[len][len];
int maxLen = 1;
int maxindexlow = 0;
int maxindexhigh = 0;
char[] Sarray = s.toCharArray();

``````    // initialize dig
for(int i=0;i<len;i++)
LPS[i][i] = 1;
//DP
for(int i=1;i<len;i++){
for(int j=0;j<=i-1;j++){
if((i-j)>1 && Sarray[i]==Sarray[j]){
if(LPS[i-1][j+1] == 1)
LPS[i][j] = 1;
}else{
if(Sarray[i]==Sarray[j])
LPS[i][j]=1;
}
if(LPS[i][j] == 1){
int newlen = i-j+1;
if(newlen > maxLen){
maxLen = newlen;
maxindexlow = j;
maxindexhigh = i;
}
}
}
}
String ans = s.substring(maxindexlow,maxindexhigh+1);
return ans;
}
``````

}

• Looks like you need to move the (i-j)==1, i.e. the else-statement check out of the main DP loop, will save all these checks, which reduces the constant factor.

• My DP solution also got a TLE and I don't know why...

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