max num sum
最大字段和问题，很经典，一般经典的都是去理解性记忆，但是对于递推方程一直有点疑惑，为什么只有这两种情况？
dp[j]=max{dp[j-1]+a[j],a[j]}
各种书都说这个意义在于如果前面最优解和为负直接丢弃，这是知道公式之后才可以推导的呀。。。还记得伟哥当时激动地直接课前和沈老师说起自己想到的这个线性算法
我一直在想，dp[j]只有这两种可能么？ 不可能是a[j]加上前面一部分，但是不是dp[j-1]的解？
现在证明，不可能！已知dp[j-1]是以a[j-1]为结尾的最优解，若存在dp’[j-1]+a[j]为dp[j]，则dp’[j-1]+a[j]>dp[j-1]+a[j], dp’[j-1]>dp[j-1], 则子问题有更优解，这与已知矛盾，
因为这种就是类似于数学归纳法一样，前一步推后一步，认为前面假设的是正确的，所以dp’[j-1]+a[j] 不可能是候选的最优解，若dp[j-1]>dp’[j-1]>0 || dp[j-1]>0>dp’[j-1] 则最优解dp[j-1]+a[j] 若0>dp[j-1]>dp’[j-1], 则a[j]最优解，
所以最优解只可能是max{dp[j-1]+a[j], a[j]} 不可能是某个dp’[j-1]+a[j]的
其实总结下来也就是最有子结构性质啦，我之前也不知为啥已知有点疑惑。。。