leetcode 的T5 最长回文字符串

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

package edu.contest;
//T5 动态规划
public class Solution4 {

	int arr[][] = new int[1000][1000];
	int max;
	String maxStr;

	public int calclong(String s, int i, int j) 
	{
		if (arr[i][j] > 0)
			return arr[i][j];
		if (s.charAt(i) == s.charAt(j)) 
		{
			if (i == j - 1) 
			{
				arr[i][j] = 2;
				if (arr[i][j] > max) 
				{
					max = Math.max(max, j - i + 1);
					maxStr = (String) s.subSequence(i, j + 1);
				}
			}
			if (i + 1 <= j - 1 && (calclong(s, i + 1, j - 1) != j - 1 - i)) // arr[i+1][j-1]
			{
				arr[i][j] = 0;
			} else if (i + 1 <= j - 1 && calclong(s, i + 1, j - 1) == j - 1 - i) 
			{
				arr[i][j] = calclong(s, i + 1, j - 1) + 2;
				// System.out.println("calclong"+" "+(i+1)+" "+(j-1)+"--->"+
				if (arr[i][j] > max) 
				{
					max = Math.max(max, j - i + 1);
					maxStr = (String) s.subSequence(i, j + 1);
				}
			}
		} else
			arr[i][j] = 0;
		return arr[i][j];
	}

	public String longestPalindrome(String s) {

		int max = 1;
		// System.out.println(calclong(s,1,2));
		
		for (int i = 0; i < s.length(); i++)
			arr[i][i] = 1;
		maxStr = "" + s.charAt(0);
		for (int i = 0; i < s.length(); i++)
			for (int j = i + 1; j < s.length(); j++) {
				arr[i][j] = calclong(s, i, j);
			}
		/*
		 * for(int i=0;i<s.length();i++) { for(int j=0; j<s.length(); j++)
		 * System.out.print(arr[i][j]+"\t"); System.out.println(); }
		 * System.out.println(maxStr);
		 */
		return maxStr;
	}

	public static void main(String[] args) {
		new Solution4().longestPalindrome("aaaa");
	}
}