53. 最大子数组和

给你一个整数数组 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
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

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

方法一：暴力法（当然会超时）

 就是找所有的子序列，利用两个指针找所有的连续子序列

class Solution {public int maxSubArray(int[] nums) {//暴力法int max = Integer.MIN_VALUE;//子序列最小值未知，定义一个最小值来比较int length = nums.length;for (int i = 0; i < length; ++i) {int tempMax = 0;for (int j = i; j < length; ++j) {tempMax += nums[j];if (tempMax > max) {max = tempMax;}}}return max;}
}

方法二：分治法

中间线左边的和：以中间线左边第一个数字开头的子序列的和
中间线右边的和：以中间线右边第一个数字开头的子序列的和
从中间开始左边右边加起来的子序列的最大值
而最大值一定出现在这三个值当中
分治法只是用到了递归的思想，所以开始的时候要有递归终止的条件，这里是左指针等于右指针

class Solution {public int maxSubArray(int[] nums) {    //分治法return getMax(nums,0,nums.length-1);}public int getMax(int[] nums, int l, int r) {if (l == r) {return nums[l];}int mid = (l + r) / 2;int leftSum = getMax(nums, l, mid);int rightSum = getMax(nums, mid + 1, r);int crossSum = crossSum(nums, l, r);return Math.max(crossSum, Math.max(leftSum, rightSum));}//计算中间的最大值public int crossSum(int[] nums, int l, int r) {int mid = (l + r) / 2;int leftSum = nums[mid];int leftMax = leftSum;for (int i = mid - 1; i >= l; --i) {leftSum += nums[i];if (leftMax < leftSum) {leftMax = leftSum;}}int rightSum = nums[mid + 1];int rightMax = rightSum;for (int i = mid + 2; i <= r; ++i) {rightSum += nums[i];if (rightMax < rightSum) {rightMax = rightSum;}}return leftMax + rightMax;}
}

动态规划：找最值

找最大的子序列和
每一步找到自己的最大子序列和
1、和前面合并
2、不和前面合并
到最后就确定出来了
max(nums[i],max[i-1]+nums[i])

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(nums[i], nums[i] + dp[i - 1]);max = Math.max(max, dp[i]);}return max;}
}