leetcode-最大子序和

题目：

题目链接https://leetcode-cn.com/problems/maximum-subarray/description/

背景：

        本题为非常经典的一道算法入门题，有着多种非常高效的解题方法，可以帮助答题感受到“找到问题的关键与解决问题的核心最小点”这个思维的关键。

        原本觉得此题很简单，也很容易给同事们讲清楚。实际在讲的时候发现自己也并没有把所有的方法的根本原理彻底想清楚，所以在此做一个完整的整理与分析，供自己以后回忆、以及让大家更好的理解。

        在此给大家分享五种解法，欢迎一起讨论以及使用其它方法实现。

一、无暴力，不解题

        作为个人习惯，遇到一个问题总是喜欢先考虑能否用暴力方法解决问题。因为暴力方法的思维方式最为简单，并不需要过多的考虑问题背后所蕴含的原理与思路。而且在实际生活中，可能很多问题我们使用暴力方式就足够了，这样会给开发以及运维人员都大大减少工作量。

方法一，暴力到底：

        题目要求是找出最大子序和，那么我们就把所有的子序都找出来，并且求出每个子序的和然后找到最大的一个就可以了。题目已给一个序列，我们需要做的就是确定所有能找到的开始序号与结束序号，然后把这个序号中的所有子序和都求出来。具体实现如下：

        此方法中我们用了三层循环，即在确定了某一个子序的开始序号（i）与结束序号（j）的位置后，枚举i与j中间的每个点k，计算从i到k的子序和，时间复杂度是n^3，n为序列的长度。

方法2，暴力也可以优化一点：

        在方法一中，对于i与j中间的每一个点k，我们都会计算一遍从i到k的所有数之和，其实这里我们做了很多次无用的计算，即点i到点k的数之和，为点i到点k-1的数之和，加上点k的数值。同时，我们每一个起点i开始的子序列，最长的结尾j都一定是在完整序列的最后，所以这里我们只需要两层循环就可以了：

方法3，直接暴力但是可靠的线性算法：

        在讲这个算法前，首先我们需要弄清楚的是最大子序和的这个子序所包含的一些特性：

*1）.最大子序的开始和结尾两个数一定都是正数，如果不是，那么子序列抛弃这个负数，会变的更大。

*2）.最大子序列中任何一个包含了第一个数的左子序列或者包含了最后一个数的右子序列，其和一定是正数，如果不是，那么最大子序列抛弃这一段子序，会变得更大。

*3）.最大子序列外左边第一个数开始往左任意连续多个数之和以及最大子序列外右边第一个数开始任意多个数之和，一定都是小于零的，否则最大子序列可以加上这一段数变得更大。

        由以上三个特性，我们可以实现这样一个方法：

        我们从序列的第一个数开始往后扫描。如果这个数小于零，那么它一定不会是最大子序列的第一个数，我们就继续往后扫描（特性*1）。如果这个数大于零，我们认为它可能是最大子序列的第一个数，我们从这个数开始求和，每往后扫到一个数，就把新的数加到这个和，只要这个和还大于零，这连续的子序列就可能是最大子序列的一部分（特性*2）。在不断加数的过程中，我们维护一个全局的变量，用来记录最大子序和，每次扫描一个数，都判断这个变量能否更新。一旦我们在加的过程中，子序和小于零了，那么这之前的所有数我们都直接抛弃，因为之前的数不会是最大子序列的一部分（特性*3），我们从下一个数开始计算新的子序列。

        如此操作，是需要我们对整个序列从左到右扫描一次，我们就可以在这个过程中得到最大子序和。实现如下：

时间复杂度O（n）

方法4，状态转移，动态规划：

        方法3中，可以认为我们每次都是确定了一个子序列的第一个数，然后从该数开始计算之后的子序列，其实我们也可以根据子序列的最后一个数来判断子序列的和的大小。

        最大子序列一定是以某一个序列中的数为结尾，这个数一定是正数。对序列中的每个数，都有两种可能：

（1）这个数与之前若干数组成序列，这个数是最后一个。

（2）这个数就是单独的一个序列。

        我们认为，在任意一个位置i，如果确认了i位置上的数是序列的最后一个数，那么这个序列的和最大应该是以i-1为结尾的序列加上i位置的数，和单独只有i这个位置上的数，两者中较大的一个。如果以f[i]记录以第i个位置的数为结尾的最大子序之和，具体状态转移如下：

        f[i] = max( f[i-1] + nums[i],  nums[i])

        如此我们扫描一遍整个数组，从第一个位置到最后一个位置，每次都已当前位置为子序列最后一个数，求得当前位置结束的最大子序列，同时更新全局的最大子序和，便能得到最终的最大子序和。具体实现如下：

时间复杂度O（n）

方法5，最优美的分治算法：

        最大子序列只可能有三种情况：在序列的左半部分，在序列的右半部分，横跨序列中间（包含左半部分最后一个与右半部分第一个）。所以我们需要做的就是，对比着三部分的大小，然后返回最大的一个和。

        对于中间部分，求和的办法是从中间分别求出往左的最大值与往右的最大值，两边加起来即为最大的横跨两边的子序列。

时间复杂度nlogn

        解题绝对不是把题做出来、能得到一个答案就可以。尝试不同方法的过程，其实是一个探索问题的根本问题的过程。找到了最根本的核心点，也就能相应的得到正确的解法。

        使用更快的算法来解题，不仅仅是为了炫技，更是为了能解决更艰难情况下的问题，让所有问题都变成可解的。