Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
22 lines (18 sloc) 625 Bytes
problem:
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:
这题很简单,因为是找连续的子序列(contiguous subarray),只需要走一遍数组
///////////////////////////////////////
int maxSubArray(int A[], int n)
{
int ret = A[0], sum = 0;
for(int i = 0; i < n; ++i)
{
sum = max(sum + A[i], A[i]);
ret = max(ret, sum);
}
return ret;
}