题目要求 （高频题）
给定一个整数数组nums，找到具有最大和的连续子数组（包含至少一个数字）并返回其和。
示例
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
思路方法
暴力遍历法是最容易想到的，但是由于时间消耗太高，所以就不介绍了。在这里推荐一种此类问题总常用的方法：
Kadane’s algorithm. (算是一种动态规划算法) 它需要两个变量，一个用来存储局部最优值，一个用来比较全局最优值。讲解：Why Kadane’s algorithm works?
所以问题就变成了，我们怎么去求当前的局部最优值，和全局最优。
通过遍历数组，首先我们定义变量currentNum，来表示局部最优（也就是以当前遍历元素为结尾的最大子数组），定义变量totalSum，来表示全局最优，并且都初始化为数组首元素。
算法精髓
（1）这里边我们的局部最优有两种可能：（一个是当前局部最优 + 当前遍历元素） / 另一个就只是当前遍历元素。
（2）然后全局最优就是在，上边选出的局部最优和当前全局最优中进行比较，取更大的，即可。然后对每个元素都进行上述两个操作，返回最大子数组的和。
一次遍历即可完成，时间复杂度O(n), 空间复杂度O(1)，妥妥的解决此类问题！
主要代码c++
class Solution {
public:int maxSubArray(vector<int>& nums) {
int currentNum = nums[0], totalSum = nums[0];for(int i = 1; i<nums.size(); i++){
currentNum = max(currentNum + nums[i], nums[i]);totalSum = max(totalSum, currentNum);}return totalSum;}
};
python
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""sum_ = subsum_ = float('-inf')for i in range(len(nums)):subsum_ = max(nums[i], subsum_+nums[i])sum_ = max(sum_, subsum_)"""if subsum_+nums[i] > nums[i]:subsum_ = subsum_+nums[i]else:subsum_ = nums[i] if sum_ < subsum_:sum_ = subsum_""" return sum_