53. 最大子數(shù)組和

難度中等5774收藏分享切換為英文接收動態(tài)反饋

給你一個整數(shù)數(shù)組?nums?，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

子數(shù)組?是數(shù)組中的一個連續(xù)部分。

?

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]輸出：6解釋：連續(xù)子數(shù)組?[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

進階：如果你已經(jīng)實現(xiàn)復(fù)雜度為?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;

????}

};

動態(tài)規(guī)劃比較相加前和相加后的大小，選擇大的那個，然后在于當前記錄的最大相比再選出最大的，最后返回