[Algorithm]最大子数组问题

这个问题在算法导论上给了一个O(nlogn)的解作为分治法的样例, 后来我发现O(n)可以解得更好,不管怎么说,都记了下来,更一下两年前的博客.

问题背景

输入:数天内的股价变化情况 (+10 代表上涨10, -6 代表下降6)
输出: 在某天买入,另一天卖出,获利最大的值

问题抽象

把连续十六天的股价抽象为一个数组
data = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
求解最大的子数组.

分治法求解

算法设计

采用分治的思想,利用中点把数组分为三类:
设中点为mid, 起始low, 终点high, 子数组界为i, j
(1) 左半部分: $low\leq i\leq j\leq mid$
(2) 跨越中点的部分: $low \leq i \leq mid \leq j < high$
(3) 右半部分:$mid<i \leq j \leq high$

对1,3两种情况进行分治并递归求解.
对于2,设计单独算法求解

  1. 设计求解跨越某中点的最大的子数组(MAX-CROSSED-ARRAY, 情况2)
    从中点开始向两端遍历寻找加和的最大值和得到该值的位置.
  2. 设计递归算法(MAX-SUB-ARRAY)
    设置递归基,即只有一个元素时返回该元素
    分治,返回最优策略(可能属于上述三种情况任意一种)

算法分析

时间复杂度:
$$T(n) = \left\{ \begin{array}{ll}
\Theta(1) & n=1 \\
2T(\frac{n}{2}) + \Theta(n) & n>1
\end{array} \right.
$$
由主公式可得$T(n) = \Theta (n \log n)$

算法实现

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
//Chestnutheng, 2017-01-07 10:46:03 modified.
#include <iostream>

#define MAXNUM 60000

using namespace std;

typedef struct{ //储存子数组位置和加和的结构体
int low;
int high;
int sum;
}array_info;

array_info max_crossed_array(int data[],int low,int mid,int high){ //跨越了中点的数组求最大子数组
int left_sum = -MAXNUM;
int max_left;
int sum = 0;
for(int i = mid;i >= low; --i){ //遍历中点左半的和并计算最大值
sum += data[i];
if(sum > left_sum){
left_sum = sum;
max_left = i;
}

}
int right_sum = -MAXNUM;
int max_right;
sum = 0;
for(int i = mid + 1;i <= high; ++i){ //遍历中点右半的和并计算最大
sum += data[i];
if(sum > right_sum){
right_sum = sum;
max_right = i;
}
}
array_info answer = {max_left,max_right,left_sum + right_sum}; //求出本数组的最大和并返回
return answer;
}

array_info max_child_array(int data[],int low,int high){ //求解最大子数组
if (high == low){ //递归终止条件
array_info bukket = {low,high,data[low]}; //当只有一个元素时返回它
return bukket;
}
//分治
int mid = (high + low)/2;
array_info left_bukket = max_child_array(data, low, mid);
array_info right_bukket = max_child_array(data, mid+1, high);
array_info mid_bukket = max_crossed_array(data, low, mid, high);
if(left_bukket.sum >= mid_bukket.sum && left_bukket.sum >= right_bukket.sum){
return left_bukket;
}else if(right_bukket.sum >= mid_bukket.sum && right_bukket.sum >= left_bukket.sum){
return right_bukket;
}else{
return mid_bukket; //找出最优的分治策略
}
}


int main(int argc, char const *argv[])
{
int array[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};

array_info ans = max_child_array(array, 0, sizeof(array)/sizeof(array[0]) - 1);

cout << "Sum: " << ans.sum << " ["<<ans.low << ", " <<ans.high << "]" << endl;
cout << "MAX SUB ARRAY: [";
for(int i = ans.low; i < ans.high; ++i){
cout << array[i] << ", " ;
}
cout << array[ans.high] << "]" << endl;

return 0;
}

Kadane 算法

算法思想

Kadane算法扫描一次整个数组,在每一个扫描点计算以该点数值为结束点的子数列的最大和(max_now_sum)。该子数列有可能为空,或者由两部分组成:以前一个位置为结束点的最大子数列、该位置的数值。

该算法其实用的是DP的思想, 因为子数列具有最优子结构, 即每个max_now_sum都是前一个位置为结束点的最大子数列.

实现

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
//By chestnutheng 2017-01-07 11:44:28
#include <iostream>

using namespace std;

int max_sub_array(int array[], int len){
int max_now_sum = array[0];
int max_sum = max_now_sum;
int left = 0;
int right = 0;
for(int i = 1; i < len; i++){
int now_sum = max_now_sum + array[i];
if(now_sum > array[i]){
max_now_sum = now_sum;
}else{
max_now_sum = array[i];
left = i;
}
if(max_now_sum > max_sum){
max_sum = max_now_sum;
right = i;
}
}
cout << "Sum: " << max_sum << " ARRAY: [" << left << ", " << right << "]" << endl;
return max_sum;
}

int main(){
int array[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
int sum = max_sub_array(array, sizeof(array)/sizeof(array[0]));
}