1. 力扣152.乘积最大数组

题目链接

dp[i]表示以i为终数字的最大连续子序列乘积。

由于存在负数，那么会导致最大的变最小的，最小的变最大的。所以考虑维护两个数组，dpMax[i]，dpMin[i]。

因为是连续，所以nums[i]要么和dp[i-1]乘，要么乘积重新从nums[i]开始。

=0的情况可以直接在>0情况里包含。

最后返回dpMax[i]中最大的。

			if (nums[i] >= 0){
                dpMax[i] = Math.max(nums[i], dpMax[i-1]*nums[i]);
                dpMin[i] = Math.min(nums[i], dpMin[i-1]*nums[i]);
            }
            else if (nums[i] < 0){
                dpMax[i] = Math.max(nums[i], dpMin[i-1]*nums[i]);
                dpMin[i] = Math.min(nums[i], dpMax[i-1]*nums[i]);
            }

代码

class Solution {
    public int maxProduct(int[] nums) {
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int max = nums[0];
        for (int i=1; i
            if (nums[i] >= 0){
                dpMax[i] = Math.max(nums[i], dpMax[i-1]*nums[i]);
                dpMin[i] = Math.min(nums[i], dpMin[i-1]*nums[i]);
            }
            else if (nums[i] < 0){
                dpMax[i] = Math.max(nums[i], dpMin[i-1]*nums[i]);
                dpMin[i] = Math.min(nums[i], dpMax[i-1]*nums[i]);
            }
            if(dpMax[i] > max){
                max = dpMax[i];
            }
        }
        return max;
    }
}

2. 力扣53.最大子数组和

题目链接

同样的思路。dp[i]表示以nums[i]为最后一个数字的最大子序列和。

（规定必须为最后一个数字没有错。因为要求的是连续序列。最终的连续序列必然是在某一个i索引处结束的。）

dp[i] = Math.max((dp[i-1]+nums[i]), nums[i])。要么跟之前连着继续加和，要么重新开始。

返回dp[i]中的最大值。

代码

public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i=1; i
            dp[i] = Math.max((dp[i-1]+nums[i]), nums[i]);
            if (dp[i] > max){
                max = dp[i];
            }
        }
        return max;
    }

3. 力扣5.最长回文串

题目链接

dp[i][j]表示从第i个索引字符到第j个索引字符是否为回文串。保证i<=j

分情况讨论：

1. 如果第i个索引字符和第j个索引字符不相等，则一定不是回文串，dp[i][j]为false
2. 如果相等，看长度（这样就不用考虑特殊情况了）

   1） 长度<=2，即j-i距离相差<=1。则一定是回文串。

   2）长度>2，看dp[i+1][j-1]，如果去掉首尾，中间是回文串，首尾字符还一样，那么dp[i][j]一定是回文串。

   

最重要的！遍历顺序：

因为dp[i][j]依赖于dp[i+1][j-1]，即左下方，所以一定是先遍历j（最好从大到小），再遍历i。

初始化：不需要单独考虑。

最后，为了返回最大长度的回文串，在循环内记录dp[i][j]为true时的最大长度以及最大长度时对应的首字符索引。返回s.substring(beginIndex, beginIndex+maxLength)。

代码

class Solution {
    public String longestPalindrome(String s) {
        int maxLength = 1;
        int beginIndex = 0; //有beginIndex和length就够了
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int j=0; j
            for (int i=0; i<=j; i++){
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    if ((j-i) <= 1){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j] && (j-i+1)>maxLength){
                    maxLength = j-i+1;
                    beginIndex = i;
                }
            }
        }
        return s.substring(beginIndex, beginIndex+maxLength);
    }
}

4. 力扣647.回文子串（代码随想录动规52）

题目链接

本题问的是包含的所有回文子串的数目。

包含的所有的回文子串，即所有的是回文串的s(i,j)，也即dp[i][j] = true的个数。

所以思路跟上题一样，最后结果返回dp[i][j] = true的数目总和。

代码

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int num = 0;
        for (int j=0; j
            for (int i=j; i>=0; i--){
                if(s.charAt(i) == s.charAt(j)){
                    if (j-i <= 1){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j]){
                    num++;
                }
            }
        }
        return num;
    }
}