给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.贪心算法

贪心算法（Greedy Algorithm) 简介

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}

贪婪法的基本步骤：

步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。

记录下我在理解这种解法的时候产生的疑问，和自我解答

1.如何做到根据顺序进行累加的

flag = Math.max(nums[i], flag + nums[i]); 标记位置所做的操作其实就是累加。
每次循环时都对nums[i]和flag + nums[i]进行比较大小，我们假设为第一次循环，则flag就是数组中nums[0]
就是nums[1] 和 nums[0]+nums[1]进行比较 其实就可以理解了。
flag的值就是 nums[i] 或者 到当前位置n个循环的累加

2.是如何判断之前的子序和不是最大子序和

上一问我们得知 每次循环flag的值其实就是 nums[i] 和 到当前位置n个循环的累加 之中比较大的那一个
其实就是看前一个flag是否为负数，因为如果n+x<n那n一定是个负数
我们这里可以将前一个flag理解nums[i-1]，简单一些
如果前者大，说明nums[i-1]是个负值，最大子序和开头不应该是负值。所以flag = nums[i]
如果后者大，说明nums[i-1]是个正值。如果是正的那就累加，所以flag = nums[i]+flag
所以根本不需要判断之前的子序和不是最大子序和，只要按照条件得出flag。然后与当前最大值比较。循环结束就可以得到最大子序和。

3.如果数组全是负数呢

如果都是负数的话，无论怎么相加，结果都会越来越小。
所以只需要找最大的那个负数，就是最大子序和。
首先我们定义了初始flag 和 max 都是nums[0]
按照第二问的理解，前一个flag是个负值，最大子序和开头不应该是负值。所以flag = nums[i]
然后 max = Math.max(flag, max); 这其实就是筛选所有数值中最大的那个负数，也就是最大子序和。

/**
 * 贪心算法
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    var max = (flag = nums[0]);
    for (let i = 1; i < nums.length; i++) {
        flag = Math.max(nums[i], flag + nums[i]);
        max = Math.max(flag, max);
    }
    return max;
};

分治法

分治算法，顾名思义就是“分而治之”，即把规模较大的复杂问题拆分为若干规模较小的类似子问题，并逐个解决，最后再将各个子问题的解决结果合并，得到原始问题的结果的方法。这个技巧是很多高效算法的基础，例如快速排序算法、归并排序算法、快速傅里叶变换等等。

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

如果原问题可以分割成k个子问题，1<k<=n，且这些子问题均可解并且利用这些子问题的解求出原问题的解，那么分治方法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中