题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

方法一：贪心算法

原理：若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列。

三个变量： 前面数之和 当前数之和 最大和

int maxSubArray(int* nums, int numsSize){int preSum = 0,MaxSum = -10000,curSum = nums[0]; //初始化之前和为0，当前和为第一个元素，最大和为一个很大的负数。for(int i = 0;i < numsSize;i ++){  //遍历数组if(i==0) preSum = 0;else preSum += nums[i-1];if(preSum<0){   //如果之前和小于0，则把当前元素赋值给当前和，之前和重新变为0curSum = nums[i]; preSum = 0;}else{curSum = preSum + nums[i]; //如果之前和不小于0，则把当前元素+之前和赋值给当前和，}if(curSum>MaxSum){  //如果当前和大于最大和，则赋值给最大和MaxSum = curSum;}}return MaxSum;
}

复杂度：时间O(n)，空间O(1)。

贪心算法基本要素

贪心算法通过一系列选择来得到问题的解，所做的每个选择都是当前状态下局部最好选择，即贪心选择。许多可以用贪心算法求解的问题中可以看到，它们一般具有两个重要的性质：贪心选择性质和最优子结构性质。

• 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才可以做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。

• 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

方法二：动态规划

若前一个元素大于0，则将其加到当前元素上。

int maxSubArray(int* nums, int numsSize) {int pre = 0, maxAns = nums[0];  //初始化前一个元素为0，最大子数组为0for (int i = 0; i < numsSize; i++) { //遍历数组pre = fmax(pre + nums[i], nums[i]);//返回两个数中最大的数，赋值给前一个元素maxAns = fmax(maxAns, pre);//每一个当前元素和当前最大子数组和比较}return maxAns;
}

动态规划基本要素

• 最优子结构： 利用动态规划算法求解问题的第一步就是需要刻画问题最优解的结构，并且如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。因此，判断某个问题是否适合用动态规划算法，需要判断该问题是否具有最优子结构。

Tips: 最优子结构的定义主要是在于当前问题的最优解可以从子问题的最优解得出，当子问题满足最优解之后，才可以通过子问题的最优解获得原问题的最优解。

• 重叠子问题： 适合用动态规划算法去求解的最优化问题应该具备的第二个性质是问题的子问题空间必须足够” 小 “，也就是说原问题递归求解时会重复相同的子问题，而不是一直生成新的子问题。如果原问题的递归算法反复求解相同的子问题，我们就称该最优化问题具有重叠子问题。

Tips: 在这里，我们需要注意是，与适用动态规划算法去求解的问题具备重叠子问题性质相反，前面我们介绍的分治算法递归解决问题时，问题的子问题都是互不影响，相互独立的，这个也是我们在选用动态规划算法还是分治法解决问题时的一个判断条件。

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

注：和贪心算法一样，动态规划算法只是一种思想，不是像排序算法一样有具体的代码。

方法三：分治算法

分治算法理论基础

 分治法作为一种常见的算法思想，其概念为：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，子问题的解的合并即是原问题的解。举个例子，要算16个数的和可能一下子算不出来的，但是可以通过几次一分为二（拆分），直到分成两个数、两个数一组；再对这些数两两相加，算出每组的和后，再两两相加，直到最后只剩下了一个数，就算出16个数的和（合治）。

• 适用场景

  可以用分治法解决的问题一般有如下特征：

   1.问题的规模缩小到一定的程度就可以容易地解决。此特征是大多数问题所具备的，当问题规模增大时，解决问题的复杂度不可避免地会增加。

   2.问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。此特征也较为常见，是应用分治法的前提。

   3.拆分出来的子问题的解，可以合并为该问题的解。这个特征在是否采用分治法的问题上往往具有决定性作用，比如棋盘覆盖、汉诺塔等，需要将子问题的解汇总，才是最终问题的解。

   4.拆分出来的各个子问题是相互独立的，即子问题之间不包含公共的子问题。该特征涉及到分治法的效率，如果各子问题是不独立的，则需要重复地解公共的子问题，此时用动态规划法更好。

• 使用步骤

  使用分治法的基本步骤：

   1.分解，将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

   2.解决，若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。

   3.合并，将各个子问题的解合并为原问题的解。

分治算法（Divide and Conquer）

1. 将序列从中分为左右两个子序列。

2. 递归求得两个子列的最大和。

3. 从中分点分头向左、右两边扫描，找出跨过分界线的最大子列和。

4. 输出这三个子列和最大的一个。

struct Status {int lSum, rSum, mSum, iSum;
};struct Status pushUp(struct Status l, struct Status r) {int iSum = l.iSum + r.iSum;int lSum = fmax(l.lSum, l.iSum + r.lSum);int rSum = fmax(r.rSum, r.iSum + l.rSum);int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum);return (struct Status){lSum, rSum, mSum, iSum};
};struct Status get(int* a, int l, int r) {if (l == r) {return (struct Status){a[l], a[l], a[l], a[l]};}int m = (l + r) >> 1;struct Status lSub = get(a, l, m);struct Status rSub = get(a, m + 1, r);return pushUp(lSub, rSub);
}int maxSubArray(int* nums, int numsSize) {return get(nums, 0, numsSize - 1).mSum;
}