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

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋:?連續(xù)子數(shù)組?[4,-1,2,1] 的和最大，為?6。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

思路：

令dp[i]表示以nums[i]作為末尾的連續(xù)序列的最大和，求解dp中的最大值

dp[i]只有兩種情況：

（1）序列只有一個(gè)元素，就是nums[i]

（2）序列有多個(gè)元素，從某個(gè)元素nums[p]開(kāi)始（p<i）,一直到nums[i]結(jié)尾。

第一種情況，最大和就是nums[i]

第二種情況，為dp[i-1]+nums[i]

邊界為dp[0]=nums[0]；

轉(zhuǎn)移方程為求兩種情況中的最大值 dp[i] = max(dp[i-1]+nums[i]，nums[i]）

class Solution { public:int maxSubArray(vector<int>& nums) {int size = nums.size();vector<int> dp(size, 0);dp[0] = nums[0];for(int i = 1; i < size; i++){dp[i] = max(nums[i], dp[i-1]+nums[i]);}int k = 0;for(int i = 0; i < size; i++){if(dp[i] > dp[k]){k = i;}}return dp[k];} };

?

總結(jié)

以上是生活随笔為你收集整理的leetcode--53. 最大子序和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。