53. 最大子数组和

难度中等5774收藏分享切换为英文接收动态反馈

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。（等我不那么累的时候再来想这个）

第一种对法：

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int res=0,maxs=nums[0];

        for(const auto x:nums){

          res=max(res+x,x);

          maxs=max(res,maxs);

         }

        return maxs;

    }

};

动态规划比较相加前和相加后的大小，选择大的那个，然后在于当前记录的最大相比再选出最大的，最后返回