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.
下面分别给出O(n)的动态规划解法和O(nlogn)的分治解法 本文地址
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
class
Solution {public: int
maxSubArray(int
A[], int
n) { //最大字段和问题 int
res = INT_MIN, sum = -1; for(int
i = 0; i < n; i++) { if(sum > 0) sum += A[i]; else
sum = A[i]; if(sum > res)res = sum; } return
res; }}; |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 |
class
Solution {public: int
maxSubArray(int
A[], int
n) { //最大字段和问题 return
helper(A, 0, n-1); }private: int
helper(int
A[], const
int istart, const
int iend) { if(istart == iend)return
A[iend]; int
middle = (istart + iend) / 2; int
maxLeft = helper(A, istart, middle); int
maxRight = helper(A, middle + 1, iend); int
midLeft = A[middle]; int
tmp = midLeft; for(int
i = middle - 1; i >= istart; i--) { tmp += A[i]; if(midLeft < tmp)midLeft = tmp; } int
midRight = A[middle + 1]; tmp = midRight; for(int
i = middle + 2; i <= iend; i++) { tmp += A[i]; if(midRight < tmp)midRight = tmp; } return
max(max(maxLeft, maxRight), midLeft + midRight); }}; |
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3713525.html
LeetCode:Maximum Subarray,布布扣,bubuko.com
原文：http://www.cnblogs.com/TenosDoIt/p/3713525.html