tmsofcsuba.md

题目描述：

这道题第一眼看过去还真的是一点思路都没有，可能我动态规划实在是学得太烂了吧，根本就连动态方程这四个字都没有想到，也不知道要怎么思考动态方程。一开始我还想的是思考中间一段子数组的最大子数组和，就是把问题切割嘛，但是在我看了题解之后我发现这样的切割方法肯定是不对的。题目的动态方程是：f[i] = max{f[i-1]+nums[i],nums[i]}，f[i]代表的是在第i个位置上最大的子数组和，然后我就很想当然的在一个循环里面企图用这个方程去求解问题，而且还写错了，我写的是f[i] = max{f[i-1]+nums[i],f[i-1]}，出现了非常严重的偏差。不过，尽管在我改过来之后，我发现还是不对，因为这样的方程取到的结果根本不能保证f[i-1]中的最大子数组与nums[i] 是连续的。所以我之后又增加了一个标志变量，企图用标志变量来决定两者是否满足连续性是否能够使用以上的动态方程进行取值。结果是—无论我怎么修改，都会出现瑕疵，总会到了某个数据的时候发生我们不想看见的事情，比如：中间明明隔了很多数据，代码还是把f[i-1]+nums[i] 作为了f[i] 的结果，造成了不连续性。于是，我又一次研究了题解，我发现，题解里面有两个很关键的变量：pre、maxAns 。pre指代的是之前的数之和，maxAns指代的是当前位置上最大子数组之和，相当于f[i] 。这个思路最巧妙的地方就是用pre 来指代之前的数之和，在每一次循环中，pre=max{pre+i,i} ，如果取到的是前者，说明需要把当前的数纳入当前正在检查的子数组中，如果取到的是后者，说明之前子数组的最大连续值比当前值要小，因此开始新的子数组的检查。同时辅以 maxAns=max{maxAns,pre} ，满足了在检查一串连续子数组的同时做到了对子数组中间每个位置的f[i] 进行了恰当的更新。想象一下，有一个这样的数组，第一个数据很大，但中间的数据都是-1，最后一个数据也很大，则最大子数组和应该是从头加到尾，在这种情况下，我们就需要进行一个对前子数组之和做一个和当前前数组最大子数组之和进行一个判断比较，保证在扫描中间那一串很长的-1时能够将对应的位置的值进行正确的更新。
二刷：这题其实还是划到贪心好一点，很典型的贪心，十分贪心，用一个pre来维护在这个数之前的最大连续子数组之和，加上当前值之后和当前值做比较，取大者，最大值再与更新后的pre取大者，补充一下c++的写法吧
代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        pre,maxAns = 0,nums[0]
        for i in nums:
            pre = max(pre+i,i)
            maxAns = max(pre,maxAns)
        return maxAns

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) return nums[0];
        int pre = nums[0];
        int max = pre;
        for (int i = 1; i < length; i++) {
            pre = (nums[i] + pre > nums[i]) ? (pre + nums[i]) : nums[i];
            max = (pre > max) ? pre : max;
        }
        return max;
    }
};