动态规划

4、最长回文子串

本题使用的动态规划的思想，也就是说只有 s[i+1:j-1]s[i+1:j−1] 是回文串，并且 ss 的第 ii 和 jj 个字母相同时，s[i:j]s[i:j] 才会是回文串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:  # 如果字符串长为1
            return s
        
        max = 1
        left = 0
        # dp[i][j]代表是s[i...j]是否为回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        for L in range(2, n + 1):
            for i in range(n):
                right = L + i - 1
                if right >= n:
                    break
                
                if s[i] != s[right]:
                    dp[i][right] = False
                else:
                    if right - i < 3:
                        dp[i][right] = True
                    else:
                        dp[i][right] = dp[i + 1][right - 1]

                if dp[i][right] and L > max:
                    max = L
                    left = i
        return s[left:left+max]

53、最大子数组和

看到这种区间的，可以想到动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)