题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
- 示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 - 示例 2:
输入：nums = [1]
输出：1 - 示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
子数组是数组中的一个连续部分。
暴力法
水平不够，哐哐暴力就完事了。
代码：
class Solution
{
public
int maxSubArray(int[] nums)
{
int result = Integer.MIN_VALUE; //初始化为int类型最小的值
for (int i = 0; i < nums.length; i++)
{
int sum = 0;
for (int j = i; j < nums.length; j++)
{
sum += nums[j];
if (sum > result)
{
result = sum;
}
}
}
return result;
}
}
思路大概是这样的：定义两个指针，i 指针固定指向数组第一个元素，j 指针从i 指针的位置不断往后遍历，这样对于一个数组[-2,1,-3,4,-1,2,1,-5,4]我们就可以获得:
-2
-2, 1
-2, 1, -3
-2, 2, -3, 4
...
再定义一个sum局部变量，将从 i 开始每一次获取到的元素累加起来，并判断sum是否大于result，如果sum > result 即可赋值给result，否则result保留。通过这样的方式最后我们的result里面一定是最大和。
从第一个元素开始遍历完毕后，i 指针即可指向下一个元素，sum清零，j 指针再次从 i 指针的地方向后遍历，循环往复...
分治法
非常巧妙的方法。
代码：
class Solution {
public int maxSubArray(int[] nums) {
return getMax(nums, 0, nums.length - 1); //分治函数
}
/**
* @param nums 输入的数组。
* @param left 范围的左边界。
* @param right 范围的右边界。
* @return 返回三个当中最大的值。
*/
private int getMax(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) / 2; //分界线mid
int leftMax = getMax(nums, left, mid); //左
int rightMax = getMax(nums, mid + 1, right); //右
int crossMax = getCrossMax(nums, left, right); //中间
return Math.max(Math.max(leftMax, rightMax), crossMax);
}
private int getCrossMax(int[] nums, int left, int right) {
int mid = (left + right) / 2;
int leftSum = nums[mid];
int leftMax = leftSum;
for (int i = mid - 1; i >= left; i--) {
leftSum += nums[i];
if (leftSum > leftMax)
leftMax = leftSum;
}
int rightSum = nums[mid + 1];
int rightMax = rightSum;
for (int i = mid + 2; i <= right; i++) {
rightSum += nums[i];
if (rightSum > rightMax)
rightMax = rightSum;
}
return leftMax + rightMax; //返回中间能取到的最大值
}
}
假设：
给定数组 [-9,-6，-1,2,3] 一分为二，[-9,-6,-1(中间)2,3] 中间左边的最大子序列的和是-1，右边的最大子序列的和是 5 ， 左右合并以后最大子序列和依旧是 5。
给定数组 [-1,-9,2,3,4,-6] 将它从中间一分为二，[-1,-9,2(中间)3，4,-6] 中间左边的最大子序列的和是2 ，右边的最大子序列的和是 7 ， 左右合并以后最大子序列和变为2、3、4组成的9。
结论：如果将一个数组一分为二，那么它的最大子序列将有三种情况：
一分为二
|-------在左边
|-------在中间
|-------在右边
分治法（Divide and Conquer）将一个难以直接解决的大问题，分解（Divide）成一些规模较小的相同问题，以便更容易地解决这些小问题，然后将这些小问题的解合并（Conquer）来解决原来的大问题。
特别要注意，中间这个子序列和是以中间线向左边发展递归找到的子序列和 + 以中间线向右边发展递归找到的子序列和。
动态规划
除了暴力法第一个应该想到的方法。
代码：
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
result = Math.max(result, dp[i]); //取最大子序列和
}
return result;
}
}
[-2,1,-3,4,-1,2] 每一步找到最大的子序列和。
1.和前面的子序列合并
2.不和前面的子序列合并，取自己的值
-2 它本身-2（取-2）
1 合并-1 不合并1（取1）
-3 合并-2 不合并-3 （取-2）
4 合并2 不合并4 （取4）
-1 合并3 不合并-1 （取3）
2 合并5 不合并2 （取5）
有了每一步的最大子序列和，我们只需要把其中的最大值取出来，就是数组的最大子序列和。
三要素
|--------方程式：max(本身的值，前面能取到最大的序列和的值+本身的值)
|--------初始值：第一个值-2
|--------终止值：遍历完毕为止