有这一道题，计算给定字符串中最大子符串的和，如 10 ，-2 ，3，4返回其最大子串的和，思路，假设这个子串第i位的和为dp[i]，则第i-1位的和为 dp [i-1]
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题目分析
先说下我之前的复杂思路：因为数组中可能有正有负，先将连续正、或连续负的数合并，这样列表如果全正、最大和为数组和；如果列表全负、最大和为最大的单项值；如果有正有负、合并后就会正负相间，通过比较相邻正负相加后的结果来判断是否计入最大和中。
听着很绕，实施起来也不简单，费白天功夫、通过各种特例补全了整个代码思路。接下来我们对比看下动态规划的设计。
首先要设计状态，dp [ i ] 我们定义为以数组 nums [ i ] 结尾的连续子数组的最大和——可能我们会有疑问，这个状态怎么找的？注意，动态规划最关键的就是找准状态和状态转移方程，如何找准这个要么凭理论分析、要么就是多做题积累经验。这也是我们翻看很多讲解、分析老是说动态规划不难、很简单的原因：因为人家的积累和经验在那摆着，见怪不怪了，对于刚接触这类题型的我们就好奇宝宝似的满脑袋问号。如果还记得昨天做过的背包问题，也是定义了类似在 i 位置的背包最大价值，这里定义要以 i 位置结尾的子数组，就是为了可以和 dp [ i-1 ] 建立直接联系。
有了上面的状态定义，找状态转移方程就会轻松些，在计算 dp[ i ] 时，我们可以拿到的有以 nums[i-1] 项结尾的子数组的最大和 dp[i-1] 和 nums[ i ]。根据状态定义，以 nums[i] 结尾的子数组，那么计算和一定有 nums[i] 参与，再看之前的项，倘若 dp[i-1] 为负，那么最大和就不必添加这部分；但如果其为正，则将其加入进来即可。完毕~
是的，这就完事了，上代码。
代码实现
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
# 对单项数组单独处理
if n==1:
return nums[0]
# dp[i] 为以 nums[i] 结尾的连续子数组最大和
dp = [0]*n
# 初始化 dp 数组为 n 个 0 的列表
dp[0] = nums[0]
# 遍历每一位
for i in range(1,n):
# dp[i-1]即以 nums[i-1] 结尾的子数组最大和
# 如果 dp[i-1] 非正，则不加
if dp[i-1]<=0:
dp[i] = nums[i]
# 如果正，则加起来
else:
dp[i] = dp[i-1]+nums[i]
# 返回 dp 记录列表的最大值
return max(dp)
因为我们通过对 n 位数组的一次遍历建立了所谓的状态列表，最后执行了次求最大值运输，整体时间复杂度与 n 成线性关系，即 O(n) 时间复杂度；在整个过程中，额外建立了 dp 这个长度为 n 的数组或列表，空间复杂度也为 O(n)。
