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.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
分享一段我認(rèn)為簡單易懂的代碼
class Solution {
public:
?int maxSubArray(vector& nums) {
? ? ? ? int sum = 0;
? ? ? ? int result = nums[0];
? ? ? ? for(int i = 0; i < nums.size(); i++) {
? ? ? ? ? ? sum += nums[i];
? ? ? ? ? ? result = max(sum, result);
? ? ? ? ? ? sum = max(sum, 0);? ? ? ? ?
? ? ? ? }
? ? ? ? return result;
? ? }
};
認(rèn)為這段代碼很棒，一開始無法確定subarray的起始點在哪里，代碼里可以了解到恋追，我們首先初始化結(jié)果為 nums[0],?
之后如果有max + nums[i] > max?的捂刺，那么該數(shù)一定大于0蒜田，那么sum = max（sum赦政，0）中sum就可以持續(xù)對下一個數(shù)計算總和
如果之后 0< max + nums[i] < max 的官疲，那么sum可以繼續(xù)計算下一個搂漠，防止類似 4迂卢， -2，99桐汤，1 后面有正整數(shù)出現(xiàn)
如果之后 max + nums[i] < max 且?max + nums[i] < 0 的而克，sum清零，result在這一組合中已經(jīng)出結(jié)果怔毛，sum又要從一個全新的位置開始算和
隨后员萍，result再開始像之前那樣的變化
