最大子数组和问题是一个比较有意思的问题。可以使用枚举子数组序列求最大和方法，也可是使用分治策略，动态规划也是很好的选择。然而从动态规划的角度，我们又能发现，其实一个循环就可以解决该问题。

最大子数组和 问题描述

一个数组 $A = \{a_0 , a_1 , \cdots , a_{n-1}\}$ , 其中的元素可正可负可为0，求其中的一个连续子序列，使其和最大（或仅求最大和）。

枚举方法

比较直观的方法，固定子序列的开始（$n$种），固定结束（设开始位置为i，则有$n-i$种），然后在这个范围内求和(设结束位置为j, $j-i$次操作)，时间复杂度是$O(n^3)$ 。 当然，通常我们可以在固定结尾的时候顺带求和，这样时间复杂度为$O(n^2)$。

比较直观好理解的方法。

分治策略

二分问题，把问题从中间分为两个问题，递归划分直到问题中仅包含一个元素。问题合并时，最大子数组和可能出现在三个位置：

1. 在左子问题中

2. 在右子问题中

3. 在过中间元素的序列中

1、2是子问题的解，3需要我们从中间元素开始，对左子问题，以中间元素为尾，找最大和的连续子序列；对右子问题，以中间元素下一个元素为起点，找最大和的连续子序列；（范围都在子问题的范围内）。递归方程写为$T(n) = 2T(n/2) + n$，由Master定理，知时间复杂度为O(n lg n)

为何使用分治就减少了时间复杂度呢？在合并时不还是要扫一遍吗？ 因为固定了起始和结尾点！

动态规划思想

这里不能直接从最大和这个角度出发！

要抓住连续这个关键字。我们定义子结构：

$S[i]$，表示以元素$a_i$结尾的最大连续子序列的和。

有了这个子结构，动态规划才能包含重复子问题！即才能使用动态规划的方法——或者说，这个才叫做动态规划。

此外，定义

$M[i]$， 表示从0到i序列间连续子序列的最大和。为什么分别定义$S[i]$,$M[i]$，因为$S[i]$才是动态规划的关键，而$M[i]$其实是没有必要的，使用一个M变量就足够了——只需要保存在$S[i]$过程中的最大值！

有了以上的定义，我们定义递归解：

边界条件

由于我们把$S[i]$定义为以$a_i$结束的连续子序列和，所以才可以向前递归，用$S[i-1]$来表示，这样能够保证连续。当然，如果之前的和加起当前的元素反而比当前元素值小，就肯定要舍弃之前的元素，直接选择从本元素开始。——这里我们可以找到一些奇妙的地方——这不就是说，只要前面元素连续和小于0，我们就肯定把前面元素给丢掉~从当前元素开始。

而最大和，就是记录连续子序列过程寻找中出现的最大和。

如果，我们要求出这个子序列，而非和，该添加什么呢？当$M[i] = S[i]$时，我们很清楚子序列的末尾改变了，只需要记录下来就行。所以子序列的尾比较好求（一个变量即可。因为max最大肯定是全局的最大，对应的尾也是要返回的序列的尾）。子序列的头怎么求？$S[i] = a_i$时是子序列起始点变了，但是我们是不知道这个头部是不是最终和最大的子序列的起始位置。我们可以再使用一个tmp变量，在头部改变时用tmp变量记录；在尾部变化（max变化）时把起始信息记为tmp的值。当然，同样为建立一个数组来保持伟哥位置的信息肯定是可以的。

由上，时间复杂度为$O(n)$ ， 空间复杂度为$O(n)$(只有存储$S[i]$的$n$个空间是必须的)

DP的思路没有想出来，网上找了一些也不容易看懂。直到看到手写一下求取最大子数组和序列的过程，才一下明白了。服。

一个循环

在上面的动态规划中，我们已经提及这种方法的理由了——只要从上一个起始点到目前位置的累加和大于0，那么这必然是更大和的序列的一部分；如果累加和已经小于0了，那么就该抛弃过去的负担，从当前位置开始。

这么来看，这似乎也非常直观！但是怎么就是不能这么直接想到呢？只得承认自己是不够聪明的。 = =

这个时间复杂度$O(n)$ , 空间复杂度$O(1)$

实现

leetcode对应的练习代码

扩展

1. [动态规划]对一个$n \times n$的方阵M，里面都是0、1值，找一个里面全是1的方阵，该方阵阶最大。

   当然，阶最大在这里就等价于行、列数最大的意思。

   同样，从动态规划的角度，我们学到了什么呢？对，以某个元素为尾的连续序列作为子结构！

   这里是矩阵（方阵），我么就设A[i,j]是以M[i,j]为右下角的最大元素全为1方阵的阶。有了这个子结构，得到我们的递归解：

   \[\begin{split} A[i,j] = min(A[i-1,j] , A[i,j-1] , A[i-1,j-1]) + 1 , M[i,j] = 1 \\ A[i,j] = 0 \end{split}\]

   （PS：边界条件未注明）

   为什么如此，在纸上画一个方阵，然后对照着看看就很清楚啦~。

   （开始只考虑到$A[i-1,j-1]$这个左上角元素的关系，然后再去遍历左边和上面的相应元素，看值是否为1；如果是，则可以+1，否则为1；看了方阵利用动态规划方法求最大全部为1子方阵 才明白自己考虑不够充分。不过思路还是很靠近了。觉得还是比较放心了，原来还不算太傻 - -）