动态规划无效总结--回文子串,最大子数和

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回文子串的题目很好理解，通过暴力也能做，大致情况就是用双指针，从头到尾遍历整个字符串，当字符串与反转之后的字符串相等的时候就直接输出，并且通过长度进行约束。大概代码为。

calss solution:
    def rewrord(self, s):
        n = len(s)
        s_len = 1
       for i in range(n-1):
           for j in range(i+1,n):
                if s[i:j] = s[i:j][::-1] and j - i + 1 < s_len:
                    res = s[i:j]
                    s_len = j - i + 1
 
       return res

也就是暴力选择，找到一个子串就翻转判断是否相同，随后。

随后，用动态规划就很好！

主要弄一个二维数组，其中，i是左边界，j是右边界，如果dp[i][j]是True，相当于i到j 是回文。

def reword(self,s):
    n = len(s)
    s_len = 1 # 此处单个数也是回文的
    dp = [[False] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = True
 
     for L in range(0,n):
        for i in range(n):
            j = L + i
            if j > n:
                break
            if s[i] != s[j]:
                continue
            else:
                if j -i < 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]
            if dp[i][j] and j - i + 1 >= s_len:
                star = i
                s_len = j - i + 1
     return s[star:star+s_len]

动态规划好就好在能通过状态函数改变自己的进程。

最大子数和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

思路在于如何利用这个动态规划方案，选出的最大子数和，当然在调整的时候需要考虑到当前的数是否是最大的数这一个问题，如果当前的数是正数，将前一个与数组中的数与当前的数相加，不断迭代得到结果。