DP--最大子数组和（线性-单串）

目录

题目

思路

    状态定义：dp[i]表示以i结尾的最大子数组和

    转移方程：

        计算dp[i]时，dp[0]到dp[i-1]的值已经求出

        由于是连续数组，故不存在将nums[i]逐个与dp[n]搭配求解的过程

        换言之

        dp[i]仅与dp[i-1]有关

        考虑极端情况下

        当dp[i-1]<0时，求得的结果更小，故应舍弃

        因此状态转移方程为：dp[i] = nums[i] > 0 ? nums[i] + max(dp[i-1],0) : max(dp[i-1],0)

    初始值：

        由于仅依赖比i小的O(1)个子问题，故用一个变量pre初始为0

    边界：

        dp[i-1]是否小于0，如果是<0,则舍弃

        dp[i]是否小于0，如果是，则舍弃

实现