面试题31:连续子数组的最大和

题目:输入一个整型数组,数组中有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值,要为时间复杂度为O(n)。


分析

可以这么想,假设这个数组的具有最大和的连续子数组区间为[x,y),该数组的中间元素的下标是mid。mid和[x,y)的关系又一下三种:

  • mid<x
  • mid>=y
  • x<=mid<y

所以,对于前两种情况,由于mid并不包含在最大子数组里,所以可使left=x或right=y,然后递归求解。

对于第三种情况,可从mid分别向左和右遍历,找出边界下标。

代码如下:

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
54
55
int _FindMaxCrossSumArray(vector&lt;int&gt; v,int left,int mid,int right)
{
int LeftSum=-2147483647,RightSum=-2147483647;
int LeftPos,RightPos;
int Sum=0;
int i;
for(i=mid;i&gt;=left;--i)
{
Sum+=v[i];
if(Sum&gt;LeftSum)
{
LeftSum=Sum;
LeftPos=i;
}
}
Sum=0;
for(i=mid+1;i&lt;=right;++i)
{
Sum+=v[i];
if(Sum&gt;RightSum)
{
RightSum=Sum;
RightPos=i;
}
}
Sum=0;
for(i=LeftPos;i&lt;=RightPos;++i)
{
Sum+=v[i];
}
return Sum;
}
int _FindGreatestSumOfSubArray(vector&lt;int&gt; v,int left,int right)
{
if(left&gt;=right)
return v[left];
int mid=left+(right-left)/2;
int LeftSum=_FindGreatestSumOfSubArray(v,left,mid);
int RightSum=_FindGreatestSumOfSubArray(v,mid+1,right);
int MidSum=_FindMaxCrossSumArray(v,left,mid,right);
if(LeftSum&gt;=RightSum &amp;&amp; LeftSum&gt;=MidSum)
return LeftSum;
else if(RightSum&gt;=LeftSum &amp;&amp; RightSum&gt;=MidSum)
return RightSum;
else
return MidSum;
}
int FindGreatestSumOfSubArray(vector&lt;int&gt; v)
{
if(v.size()&lt;=0)
throw new exception();
return _FindGreatestSumOfSubArray(v,0,v.size()-1);
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>