求给定数组的最大子数组

话说前天晚上被网易虐的也是够惨,3道编程题做出来两道,一个运行超时,一个通过率为70%。其实考的是动态规划之类的东西,只可惜我当时没有好好学。虽然牛客网服务器挂了导致考试延长一个小时,但这对我并没有什么实质帮助,不会还是不会呀。

今天开始啃《算法导论》,每天一个算法,坚持!

简单看了下分治这一节,照着书上的思想敲出了”给定数组的最大子数组”的代码,如下:

FindMidMaxSum(const vector<int>& v, int left, int mid, int right, int* MaxLeft, int* MaxRight)
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
{
if (left &gt; mid || mid &gt; right)
return 0;
int LeftSum = 0;
int RightSum = 0;
int LeftMaxSum = INT_MIN;
int RightMaxSum = INT_MIN;
int i;
for (i = mid;i &gt;= left;--i)
{
LeftSum += v[i];
if (LeftSum &gt; LeftMaxSum)
{
LeftMaxSum = LeftSum;
*MaxLeft = i;
}
}
for (i = mid + 1;i &lt;= right;++i)
{
RightSum+= v[i];
if (RightSum &gt; RightMaxSum)
{
RightMaxSum = RightSum;
*MaxRight = i;
}
}
return LeftMaxSum + RightMaxSum;
}
int FindMaxSubArray(const vector&lt;int&gt;&amp; v, int left, int right,int* i,int* j)
{
if (left &gt; right)
return 0;
if (left == right)
{
*i = *j = left;
return v[left];
}
int MaxLeft1, MaxRight1,MaxLeft2, MaxRight2,MaxLeft3, MaxRight3;
int mid = left + (right - left) / 2;
int LeftSum = FindMaxSubArray(v, left, mid, &amp;MaxLeft1, &amp;MaxRight1);
int RightSum = FindMaxSubArray(v, mid + 1, right, &amp;MaxLeft2, &amp;MaxRight2);
int MidSum = FindMidMaxSum(v, left, mid, right, &amp;MaxLeft3, &amp;MaxRight3);
if (LeftSum &gt;= RightSum &amp;&amp; LeftSum &gt;= MidSum)
{
*i = MaxLeft1;
*j = MaxRight1;
return LeftSum;
}
else if (RightSum &gt;= LeftSum &amp;&amp; RightSum &gt;= MidSum)
{
*i = MaxLeft2;
*j = MaxRight2;
return RightSum;
}
else
{
*i = MaxLeft3;
*j = MaxRight3;
return MidSum;
}
}
int calculateMax(vector&lt;int&gt; prices)
{
int i;
vector&lt;int&gt; v;
int left, right;
for (i = 1;i &lt; prices.size();++i)
{
v.push_back(prices[i] - prices[i - 1]);
cout &lt;&lt; prices[i] - prices[i - 1]&lt;&lt;" ";
}
cout &lt;&lt; endl;
int sum1=FindMaxSubArray(v, 0, v.size() - 1, &amp;left, &amp;right);
int a = left;
int b = right;
int sum2 = FindMaxSubArray(v, 0, left - 1, &amp;left, &amp;right);
left = a;
right = b;
int sum3 = FindMaxSubArray(v, right, v.size()-1, &amp;left, &amp;right);
if (sum1 &lt;= sum2 &amp;&amp; sum1 &lt;= sum3)
{
if (sum2 &lt; 0)
return sum3;
if (sum3 &lt; 0)
return sum2;
return sum2 + sum3;
}
else if (sum2 &lt;= sum1 &amp;&amp; sum2 &lt;= sum3)
{
if (sum1 &lt; 0)
return sum3;
if (sum3 &lt; 0)
return sum1;
return sum1 + sum3;
}
else
{
if (sum1 &lt; 0)
return sum2;
if (sum2 &lt; 0)
return sum1;
return sum1 + sum2;
}
}

<!--more-->

代码的github地址