比如对于数组[1,-2,3,5,-1,2] 最大子数组和是sum[3,5,-1,2] = 9, 我们要求函数输出子数组和的最大值,并且返回子数组的左右边界(下面函数的left和right参数).
本文我们规定当数组中所有数都小于0时，返回数组中最大的数（也可以规定返回0，只要让以下代码中maxsum初始化为0即可，此时我们要注意-1 0 0 0 -2这种情形，特别是如果要求输出子数组的起始位置时，如果是面试就要和面试官问清楚）
以下代码我们在PAT 1007. Maximum Subsequence Sum测试通过,测试main函数如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int
main()
{
int
n;
scanf
(
"%d"
, &n);
vector<
int
>vec(n);
for
(
int
i = 0; i < n; i++)
scanf
(
"%d"
, &vec[i]);
int
left, right;
int
maxsum = maxSum1(vec, left, right);
//测试时替换函数名称
if
(maxsum >= 0)
printf
(
"%d %d %d"
, maxsum, vec[left], vec[right]);
else
printf
(
"0 %d %d"
, vec[0], vec[n-1]);
}
|
参考：编程之美2.14 求数组的子数组之和的最大值
算法1：最简单的就是穷举所有的子数组，然后求和，复杂度是O（n^3）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int
maxSum1(vector<
int
>&vec,
int
&left,
int
&right)
{
int
maxsum = INT_MIN, sum = 0;
for
(
int
i = 0; i < vec.size(); i++)
for
(
int
k = i; k < vec.size(); k++)
{
sum = 0;
for
(
int
j = i; j <= k; j++)
sum += vec[j];
if
(sum > maxsum)
{
maxsum = sum;
left = i;
right = k;
}
}
return
maxsum;
}
|
算法2: 上面代码第三重循环做了很多的重复工作,稍稍改进如下,复杂度为O(n^2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int
maxSum2(vector<
int
>&vec,
int
&left,
int
&right)
{
int
maxsum = INT_MIN, sum = 0;
for
(
int
i = 0; i < vec.size(); i++)
{
sum = 0;
for
(
int
k = i; k < vec.size(); k++)
{
sum += vec[k];
if
(sum > maxsum)
{
maxsum = sum;
left = i;
right = k;
}
}
}
return
maxsum;
}
|
算法3: 分治法, 下面贴上编程之美的解释, 复杂度为O(nlogn)
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
//求数组vec【start，end】的最大子数组和，最大子数组边界为[left，right]
int
maxSum3(vector<
int
>&vec,
const
int
start,
const
int
end,
int
&left,
int
&right)
{
if
(start == end)
{
left = start;
right = left;
return
vec[start];
}
int
middle = start + ((end - start)>>1);
int
lleft, lright, rleft, rright;
int
maxLeft = maxSum3(vec, start, middle, lleft, lright);
//左半部分最大和
int
maxRight = maxSum3(vec, middle+1, end, rleft, rright);
//右半部分最大和
int
maxLeftBoeder = vec[middle], maxRightBorder = vec[middle+1], mleft = middle, mright = middle+1;
int
tmp = vec[middle];
for
(
int
i = middle-1; i >= start; i--)
{
tmp += vec[i];
if
(tmp > maxLeftBoeder)
{
maxLeftBoeder = tmp;
mleft = i;
}
}
tmp = vec[middle+1];
for
(
int
i = middle+2; i <= end; i++)
{
tmp += vec[i];
if
(tmp > maxRightBorder)
{
maxRightBorder = tmp;
mright = i;
}
}
int
res = max(max(maxLeft, maxRight), maxLeftBoeder+maxRightBorder);
if
(res == maxLeft)
{
left = lleft;
right = lright;
}
else
if
(res == maxLeftBoeder+maxRightBorder)
{
left = mleft;
right = mright;
}
else
{
left = rleft;
right = rright;
}
return
res;
}
|
算法4: 动态规划, 数组为vec[]，设dp[i] 是以vec[i]结尾的子数组的最大和，对于元素vec[i+1], 它有两种选择：a、vec[i+1]接着前面的子数组构成最大和，b、vec[i+1]自己单独构成子数组。则dp[i+1] = max{dp[i]+vec[i+1], vec[i+1]}
如果不考虑记录最大子数组的位置，于是有以下代码： 本文地址
|
1
2
3
4
5
6
7
8
9
10
|
int
maxSum_(vector<
int
>&vec)
{
int
maxsum = INT_MIN, sum = 0;
for
(
int
i = 0; i < vec.size(); i++)
{
sum = max(sum + vec[i], vec[i]);
maxsum = max(maxsum, sum);
}
return
maxsum;
}
|
对以上代码换个写法，并记录最大子数组的位置
|
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
|
int
maxSum4(vector<
int
>&vec,
int
&left,
int
&right)
{
int
maxsum = INT_MIN, sum = 0;
int
begin = 0;
for
(
int
i = 0; i < vec.size(); i++)
{
if
(sum >= 0)
{
sum += vec[i];
}
else
{
sum = vec[i];
begin = i;
}
if
(maxsum < sum)
{
maxsum = sum;
left = begin;
right = i;
}
}
return
maxsum;
}
|
如果数组是循环的，该如何呢
这时分两种情形（图中红色方框表示求得的最大子数组，left、right分别是子数组的开始和结尾）：
（1）如下图最大的子数组没有跨过vec[n-1]到vec[0], 这就是每循环的情况
（2）如下图，最大的子数组跨过vec[n-1]到vec[0]
对于第二种情形，相当于从原数组中挖掉了一块(vec[right+1], …, vec[left-1]) ,那么我们只要使挖掉的和最小即可，求最小子数组和最大子数组类似，代码如下，以下代码在九度oj1572首尾相连数组的最大子数组和通过测试（测试需要，以下代码当数组全是负数时，输出0）：
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
int
maxSumCycle(vector<
int
>&vec,
int
&left,
int
&right)
{
int
maxsum = INT_MIN, curMaxSum = 0;
int
minsum = INT_MAX, curMinSum = 0;
int
sum = 0;
int
begin_max = 0, begin_min = 0;
int
minLeft, minRight;
for
(
int
i = 0; i < vec.size(); i++)
{
sum += vec[i];
if
(curMaxSum >= 0)
{
curMaxSum += vec[i];
}
else
{
curMaxSum = vec[i];
begin_max = i;
}
if
(maxsum < curMaxSum)
{
maxsum = curMaxSum;
left = begin_max;
right = i;
}
///////////////求和最小的子数组
if
(curMinSum <= 0)
{
curMinSum += vec[i];
}
else
{
curMinSum = vec[i];
begin_min = i;
}
if
(minsum > curMinSum)
{
minsum = curMinSum;
minLeft = begin_min;
minRight = i;
}
}
if
(maxsum >= sum - minsum)
return
maxsum;
else
{
left = minRight+1;
right = minLeft-1;
return
sum - minsum;
}
}
|
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3698246.html，如需转载请自行联系原作者
