随笔(3)–Leetcode 53

废话不说，直接看题目

这个题目属于非常常见的一类，这是因为在实际中我们要求连续最大盈利。当然，这种题也是有暴力解法的，就是任选两个数字，计算,然后在得出最大值就可以了，这样做的复杂度是。既然这样，我们不禁要问，能不能扫描一次就得出结果呢?

对于一个index i,我们定义，就是前i项的和，那么对于每个i，S[i]是固定的，接下来我们需要确定起点j从而最大化,也就是说，如果我们最小化S[j]，那么S[i]-S[j]就是以i为终点的max subarray sum。我们遍历i取出最大值就可以了。代码如下：

注意这里有一个陷阱，两个if条件是不能颠倒的，这里contagious的定义是至少要选一个元素，不能一个都不选，如果两个if条件颠倒了，出现[-1,-1,-1]这种数列，结果会输出零，这是不对的，需要注意