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);
}
};
|
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3713525.html，如需转载请自行联系原作者
