题目：
Given an integer arraynums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
几百年没做，差点以为是prefix sum或者sliding window。也是看了答案才知道是dp，以及并没有一次性写出来……当个复读机重复一下以前写的，我觉得写挺好：
这道题的思路其实很简单，题目要求找出数组中连续的几个数字之和的最大。由于数组是连续的，因此我们以"以nums[i]结尾的数组"为基准来划分子问题，把它表示为sum[i]，那么sum[i]只有两种情况，要么是nums[i]自己白手起家，要么是在它前面的sum[i - 1]的基础之上锦上添花，因此这个问题就变成了sum[i] = max(sum[i - 1] + nums[i], nums[i])。
因为这题的dp状态转移比较简单，只depends on前一个的状态，所以其实可以不用存数组直接用变量表示。
用数组：
class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); result = Math.max(result, dp[i]); } return result; } }用变量（以及根据gpt老师这是一个算法名字叫Kadane's Algorithm）：
class Solution { public int maxSubArray(int[] nums) { int currSum = 0; // can use 0 as it's calculated in the for loop int maxSum = nums[0]; for (int i = 0; i < nums.length; i++) { currSum = Math.max(nums[i], currSum + nums[i]); maxSum = Math.max(maxSum, currSum); } return maxSum; } }番外：为啥不是prefix sum或者sliding window？according to GPT老师：
为啥不用prefix sum：
我们需要找到最大子数组和，而不是计算某个已知区间的和。
如果直接枚举所有区间：
左端点有 \(O(n)\) 种选择。
右端点有 \(O(n)\) 种选择。
使用前缀和可以让每次区间求和降到 \(O(1)\)。
总时间复杂度仍然是 \(O(n^2)\)。
不过，Prefix Sum 也可以进一步优化到 \(O(n)\)！所以并不是说这题不能用前缀和，而是前缀和不是最直观的解题思路。
为啥不用sliding window：
Sliding Window 通常适用于这样的场景：
窗口满足某个条件时，尝试扩大窗口；
窗口不满足条件时，尝试缩小窗口；
缩小窗口能够让我们有规律地恢复条件。
例如，数组全是正数时，寻找“和不超过 \(K\) 的最长连续子数组”，就可以用滑动窗口。因为右端点右移会让窗口和增大，左端点右移会让窗口和减小。
但 Maximum Subarray 的数组可以包含任意正数和负数。
滑动窗口最重要的前提是：窗口条件随左右端点移动，具有足够的单调性或可维护性。 这道题的最大子数组和没有提供常规滑动窗口所需的性质。
以下来自久远的2019:
这道题可是两年前在水算法作业的时候做过的题，翻了以前的博客发现以前不会做，巧了，现在也不会做。题目一看就想到了动态规划，可是却没想出来到底怎么划分子问题，看了以前的记录才想到解法，然后瞬间就写出了代码（并发现之前那个代码绝壁不是我写的以前的我怎么这么水啊）。
这道题的思路其实很简单，题目要求找出数组中连续的几个数字之和的最大。由于数组是连续的，因此我们以"以nums[i]结尾的数组"为基准来划分子问题，把它表示为sum[i]，那么sum[i]只有两种情况，要么是nums[i]自己白手起家，要么是在它前面的sum[i - 1]的基础之上锦上添花，因此这个问题就变成了sum[i] = max(sum[i - 1] + nums[i], nums[i])。
我自己写的代码如下，时间复杂度O(n)，运行时间12ms，只打败了5%，看了下以前抄的代码发现可以用max()来简化那些if们：
class Solution { public: int maxSubArray(vector<int>& nums) { int max = nums[0]; int sum = nums[0]; for (int i = 1; i < nums.size(); i++) { if (sum + nums[i] < nums[i]) { sum = nums[i]; } else { sum += nums[i]; } if (sum > max) { max = sum; } } return max; } };使用max()以后代码看起来清晰整洁的版本：
class Solution { public: int maxSubArray(vector<int>& nums) { int currentSum =nums[0], totalSum = nums[0]; for(int i=1; i<nums.size(); i++) { //Current max sum is either the current element OR current element + Previous Maximum subarray) currentSum = max(nums[i], currentSum+nums[i]); //If the current maximum array sum is greater than the global total. Update it totalSum = max(totalSum, currentSum); } return totalSum; } };2020.10.1 Java：依旧差点没想到dp表达式，卑微。
Runtime: 1 ms, faster than 68.70% of Java online submissions for Maximum Subarray.
Memory Usage: 38.9 MB, less than 96.46% of Java online submissions for Maximum Subarray.
class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = dp[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); if (dp[i] > max) { max = dp[i]; } } return max; } }还有另一种和这个思路很相似的解法，设置一个currentSum和一个totalSum，分别存储截至当前nums[i]的sum和全局的最大值，代码如下：
int maxSubArray(vector<int>& nums) { int currentSum = 0, totalSum = INT_MIN; for(int i=0; i<nums.size(); i++) { //Sum till this point ======= Current Sum till this point + this element currentSum = currentSum + nums[i]; //If the current maximum array sum is greater than the global total. Update it totalSum = max(totalSum, currentSum); //If you get current as less thn 0 then its no point in carrying forward. Make it 0 currentSum = max(0,currentSum); } return totalSum; }感觉这种解法的第一句和第三句的合体就是DP解法的第一句，假设当前遇到的nums[i]会使totalSum减小，那么currentSum将保存当前的结果，并在nums[i + 1]的时候加入nums[i + 1]与totalSum比较。（理解的感觉不是特别到位，强行解释了一番，因为这个方法让我自己想我是想不到的，只能在了解方法以后自己在纸上模拟一遍）以上两个代码均来自于https://leetcode.com/problems/maximum-subarray/discuss/118509/C++-Kadane's-Algorithm，总结的很好
然后看到题目底下还有个follow up，说是可以用分治算法来解决，看了下以前的记录发现是没有的，想了一会儿还是想不到分治的解法。看了discussion里大佬的解法，大概就是，把原始的数组分成左右两半分别递归，最后要找的max的可能性有三种，要么完全是在已经分成的左右两边的一边中，要么就可能是横跨左右两边并包含中间的元素。然而就算是知道了这种解法但依旧不会写代码orz 真实的递归无能了。基本上抄着大佬的代码打出了如下代码并加了点自己的注释，运行时间8ms，击败了35%的C++ submission：
class Solution { public: int maxSubArray(vector<int>& nums) { return maxSub(nums, 0, nums.size() - 1); } int maxSub(vector<int>& nums, int l, int r) { if (l > r) { return INT_MIN; } // recursion for left and right part int m = (l + r) / 2; int lmax = maxSub(nums, l, m - 1); int rmax = maxSub(nums, m + 1, r); // find out the max closest to the middle int ml = 0, mr = 0; int sum = 0; for (int i = m - 1; i >= l; i--) { sum += nums[i]; ml = max(ml, sum); } sum = 0; for (int i = m + 1; i <= r; i++) { sum += nums[i]; mr = max(mr, sum); } // return either the max in the left/right, or combines both side and the middle return max(max(lmax, rmax), ml + mr + nums[m]); } };这份代码的参考来源：https://leetcode.com/problems/maximum-subarray/discuss/20452/C%2B%2B-DP-and-Divide-and-Conquer
