【每日刷题】 动规-力扣152、53、5、647

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]  
代码
 
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]  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
    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
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    if ((j-i) 
                        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);
    }
}

    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 
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j]){
                    num++;
                }
            }
        }
        return num;
    }
}