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(vectorint nums) { int nnums.size(); if(n1) return 0; int Sum0; int max_sum-INT_MAX; int left0; int right0; while(rightn){ if(Sum0){ leftright; Sumnums[right]; max_summax_sumSum?max_sum:Sum; right; continue; } Sumnums[right]; max_summax_sumSum?max_sum:Sum; right; } return max_sum; } };