一、实践题目名称
最大子段和
二、问题描述
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。
要求算法的时间复杂度为O(n)
三、算法描述
分析题目，要求最大子段和，用N表示输入数组，S[i]记录以下标i结尾的子段和，S[i]的最大值即为最大子段和，而S[i]会依赖前面的子问题S[i - 1]，根据动态规划，即递归方程为：S[i] = max {S[i - 1] + N[i], N[i]}，边界条件即S[1] = N[1]。用k记录数组种负数个数，如果k会等于n及输入全为负数，输出0，否则，进行动态规划，用maxsum记录最大子段和即S[i]的最大值，填数组S过程中更新maxsum的值，填完数组S，得到的maxsum就是最大子段和，输出maxsum
四、问题求解
1、根据最优子结构性质，列出递归方程式
S[i] = max {S[i - 1] + N[i], N[i]} （1 <= i <= n）
2、给出填表法中的表的维度、填表范围和填表顺序
一维S[i]数组，从S[1]填至S[n]，从左至右
3、分析该算法的时间和空间复杂度
关键语句在一个for循环中，所以时间复杂度为 T(n) = O(n)
只需记录输入数的数组N和记录子段和的数组S，即空间复杂度为O(n)
五、心得体会
粗心导致的问题：一开始设置数组N以及存储子段和的数组S的大小是n，然后两个数组都是从1开始存的，就造成了不够存的溢出错误，后面修改大小为n + 1就正确了
这题用到了动态规划的思想，通过pta的几道题练习后，我对动态规划进一步了解了
动态规划总结
哪些问题可以使用动态规划
-
最优子结构（必须有）
原问题的解包含子问题的解
-
子问题重叠（不是必须有的）
许多子问题会重复求解，用表格存储子问题的解，要用时在查找
注：子问题不重叠既可以使用分治法，也可以用动态规划。但重叠时用分治法重复求解子问题导致效率低下
-
无后效性（必须有）
自下而上地求解，当前子问题求解只与下方的子问题有关
求解分析步骤
有向无环图
-
状态
分析当前状态
-
阶段
根据拓扑序划分阶段，某几个子问题求解后才能求解下一个子问题，它们就分为不同阶段
-
决策
写出状态转移方程 == 递归方程