【问题描述】

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.

【问题分析】

【源代码】

class Solution {public:    int maxSubArray(vector<int>& nums) {        int max = nums[0];        int sum = 0;        int i = 0;        while (i < nums.size()) {        	sum += nums[i];        	if (sum > max) {        		max = sum;        	}        	if (sum < 0) {        		sum = 0;        	}        	i++;        }        return max;    }};方法二（分治方法）：
/**sum-------the total sum of the subarray.leftmx----largest sum starting from the left most element.rightmx---largest sum starting ending the right most element.mx--------largest sum of the subarray.**/class Solution {public:    int maxSubArray(vector<int>& nums) {        if (nums.size() == 0) {        	return 0;        }        if (nums.size() == 1) {            return nums[0];        }        int mx,leftmx,rightmx,sum = 0;        maxSubArray(nums, 0, nums.size()-1, mx, leftmx, rightmx, sum);        return mx;    }PRivate:	void maxSubArray(vector<int>& nums, int left, int right, int& mx, int& leftmx, int& rightmx, int& sum) {		if (left == right) {			mx = leftmx = rightmx = sum = nums[left];		} else {			int leftmx1, sum1, rightmx1, mx1 = 0;			int leftmx2, sum2, rightmx2, mx2 = 0;			int mid = (left + right) / 2;			maxSubArray(nums, left, mid, mx1, leftmx1, rightmx1, sum1);			maxSubArray(nums, mid+1, right, mx2, leftmx2, rightmx2, sum2);			mx = max(max(mx1, mx2), rightmx1 + leftmx2);			leftmx = max(leftmx1, sum1 + leftmx2);			rightmx = max(rightmx2, sum2 + rightmx1);			sum = sum1 + sum2;		}	}};