子串类算法问题的分析思路

发表于 分类于 阅读次数：

解决思路

  1. 暴力解法
  2. 滑动窗口
  3. 动态规划

特点

  1. 最大子序和：连续、子串和最大

    1
    2
    dp[i]：以nums[i]为结尾的子串的最大和
    dp[i] = max(dp[i-1] + nums[i], nums[i])

  2. 最长回文子串：连续、子串为回文

    1
    2
    dp[i][j]：s[i]到s[j]是否为回文
    dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
    1
    2
    3
    4
    5
    6
    for (int k = 0; k < s.length(); k++) {
        for (int i = 0, j = k; i < s.length() && j < s.length(); i++, j++) {
            boolean isSym = s.charAt(i) == s.charAt(j);
            dp[i][j] = isSym && ((j <= (i + 1)) || (dp[i + 1][j - 1] == true));
        }
    }