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.

click to show more practice.

Subscribe to see which companies asked this question

目前就想到了动态规划的方法，而且还不是很快，两个下标，每次B下标后移，并把对应的值加入temp，如果temp > nowmax ,则替换，若temp 《＝ 0 则A下标前移。目前没想到更好的做法。效率不算很高。


class Solution {
public:
int maxSubArray(vector& nums) {
int start = 0;
int end = 0;
int nowmax = 0;
int temp = 0;
if(nums.size() == 0)
{
return 0;
}
else
{
nowmax = nums[0];
}
for(start = 0 ;start < nums.size();start++) { temp = 0; for(end = start;end nowmax)
nowmax = temp;
if(temp <= 0) break; } } return nowmax; } };