題目：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array?[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray?[4,-1,2,1]?has the largest sum =?6.

題解：

　　遍歷所有組合，更新最大和。

Solution 1 (TLE)

class Solution { public:int maxSubArray(vector<int>& nums) {int n = nums.size(), result = nums[0];for(int i=0; i<n; ++i) {int tmp = nums[i];result = max(tmp,result);for(int j=i+1; j<n; ++j) {tmp += nums[j];result = max(tmp,result);} } return result;} };

　　可以看做動態(tài)規(guī)劃的簡略版，見Solution 5

Solution 2 ()

class Solution { public:int maxSubArray(vector<int>& nums) {int n = nums.size(), result = nums[0], tmp = 0;for(int i=0; i<n; ++i) {tmp = max(tmp + nums[i], nums[i]);result = max(result, tmp); } return result;} };

　　貪心算法：The idea is to find the largest difference between the sums when you summing up the array from left to right. The largest difference corresponds to the sub-array with largest sum

Solution 3 ()

class Solution { public:int maxSubArray(vector<int>& nums) {int sum = 0, minsum = 0, result = nums[0], n = nums.size();for(int i = 0; i < n; i++) {sum += nums[i];if(sum - minsum > res) result = sum - minsum;if(sum < minsum) minsum = sum;}return result;} };

　　分治法：

Solution 4 ()

　　DP算法：維護一個一維數(shù)組。

Solution 5 ()

class Solution { public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n,0);//dp[i] means the maximum subarray ending with nums[i];dp[0] = nums[0];int max = dp[0];for(int i = 1; i < n; i++){dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);max = Math.max(max, dp[i]);} return max;} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/Atanisi/p/6730921.html

總結

以上是生活随笔為你收集整理的【LeetCode】053. Maximum Subarray的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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