13 最大子数组和

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

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

思路

1、核心思想就是定义窗口累加，如果当前累加值是负数，那么累加清零（），窗口从下一个数开始，从下一个数开始累加。

2、定义一个窗口和的数 Num和记录最大窗口和的数NumMax。定义一个左指针和右指针，左指针指向窗口开始的位置，右指针指向窗口结束的位置。

3、进入循环，将右指针加入窗口，计算窗口和，对比窗口和与NumMax谁更大，NumMax记住最大的值。

4、比较当前窗口和与下个数字的和大还是下个数字大。

5、假如下一个数字更大，那么窗口left和right重新指向下一个数字。

6、假如当前窗口和加上下一个数字更大，那么right继续往前走，计算窗口和。

7、判断循环结束条件，当right走到数组边界时结束，返回NumMax。

class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); if(n<1) return 0; int Sum=0; int max_sum=-INT_MAX; int left=0; int right=0; while(right<n){ if(Sum<0){ left=right; Sum=nums[right]; max_sum=max_sum>Sum?max_sum:Sum; right++; continue; } Sum+=nums[right]; max_sum=max_sum>Sum?max_sum:Sum; right++; } return max_sum; } };