5. 最长回文子串 - 力扣（LeetCode） (opens new window)

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int ans = 1; // 最长回文子串的长度，擂台
        int leftIndex = 0, rightIndex = 0; // 最长回文子串的左，右位置
        boolean[][] dp = new boolean[n][n]; // dp[i][j],i->j的串是否回文
        // 初始化长度为1的回文子串
        for (int i = 0;i < s.length(); i++) {
            dp[i][i] = true;
        }
        // 初始化长度为2的回文子串
        for (int i = 0; i + 1 < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                if (ans < 2) {
                    ans = 2;
                    leftIndex = i;
                    rightIndex = i + 1;
                }
            } 
        }
        // 遍历长度大于2的回文子串
        for (int len = 3; len <= s.length(); len++) {
            for (int left = 0; left < s.length(); left++) {
                int right = left + len - 1;
                if (right >= s.length()) break;
                if (s.charAt(left) == s.charAt(right) && dp[left + 1][right -1]) {
                    dp[left][right] = true;
                    if (len > ans) {
                        ans = len;
                        leftIndex = left;
                        rightIndex = right;
                    }
                }
            }
        }
        return s.substring(leftIndex, rightIndex + 1);
    }
}

53. 最大子数组和 - 力扣（LeetCode） (opens new window)

dp 数组的含义：以 nums[i] 为结尾的「最⼤⼦数组和」为 dp[i]

dp[i] 有两种「选择」，要么与前⾯的相邻⼦数组连接，形成⼀个和更⼤的⼦数组；要么不与前⾯的⼦数组连接，⾃成⼀派，⾃⼰作为⼀个⼦数组。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        // base case
        dp[0] = nums[0];
        // 状态转移⽅程
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}