重庆响应式网站建设公司_建站之星备案_it培训机构推荐_网络推广员要怎么做

示例 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);}}} elsearr[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");}
}