最大子序列问题

最大子序列问题是一个经典的算法问题,在”Data Structures and Algorithm Analysis in C”一书第2章中介绍了此问题,并给出了复杂度从O(n^3)至O(n)的4种解法,这里对此问题稍作扩展总结一下。

问题描述

给定一个数字序列,求出其最大子序列和,并给出对应的区间。如给定{-2, 11, -4, 13, -5, -2},最大子序列和为20,对应的区间为[1, 3]。(下标从0开始)

输出区间中至少包含一个元素,即若输入的数全部为负数,需输出最大的那个负数。

若有多个子序列和相同,返回任意一个子序列区间即可。

函数原型:

1
int MaxSubsequenceSum(const int A[], int N, int * left, int * right);

其中leftright为输出区间。

注:原始问题中,不需要输出对应区间,且若均为负数输出0,此处进行了一些扩展。

O(n^2)算法

直接循环求解,代码如下:

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
int MaxSubsequenceSum(const int A[], int N, int * left, int * right) {
int i, j;
int maxIndex, maxNum, tmpSum, maxSum;

maxNum = A[0];
maxIndex = 0;
maxSum = 0;
for (i = 0; i < N; i++) {
if (A[i] > maxNum) {
maxIndex = i;
maxNum = A[i];
}

tmpSum = 0;
for (j = i; j < N; j++) {
tmpSum += A[j];
if (tmpSum > maxSum) {
maxSum = tmpSum;
*left = i;
*right = j;
}
}
}

if (maxNum <= 0) {
*left = maxIndex;
*right = maxIndex;
return maxNum;
}

return maxSum;
}

O(nlog(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
int MaxSubsequenceSum(const int A[], int N, int * left, int * right) {
return MaxSubSumIterate(A, 0, N - 1, left, right);
}

int MaxSubSumIterate(const int A[], int Nl,int Nr, int * left, int * right) {
int leftMax, leftMaxLeft, leftMaxRight;
int rightMax, rightMaxLeft, rightMaxRight;
int middleMax, middleMaxLeft, middleMaxRight;
int tmpSum;
int center;
int i;

/* Base case */
if (Nl == Nr) {
*left = Nl;
*right = Nr;
return A[Nl];
}

/* Left & Right */
center = (Nl + Nr) / 2;
leftMax = MaxSubSumIterate(A, Nl, center, &leftMaxLeft, &leftMaxRight);
rightMax = MaxSubSumIterate(A, center + 1, Nr, &rightMaxLeft, &rightMaxRight);

/* Middle */
middleMax = 0;
tmpSum = 0;
middleMaxLeft = center + 1;
middleMaxRight= center;

for (i = center; i >= Nl; i--) {
tmpSum += A[i];
if (tmpSum > middleMax) {
middleMax = tmpSum;
middleMaxLeft = i;
}
}

tmpSum = middleMax;
for (i = center + 1; i <= Nr; i++) {
tmpSum += A[i];
if (tmpSum > middleMax) {
middleMax = tmpSum;
middleMaxRight = i;
}
}

/* middleMax == 0 说明middle无效 */
if (middleMax > 0 && middleMax > leftMax && middleMax > rightMax) {
*left = middleMaxLeft;
*right = middleMaxRight;
return middleMax;
}
else {
if (leftMax >= rightMax) {
*left = leftMaxLeft;
*right = leftMaxRight;
return leftMax;
}
else {
*left = rightMaxLeft;
*right = rightMaxRight;
return rightMax;
}
}
}

O(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
int MaxSubsequenceSum3(const int A[], int N, int * left, int * right) {
int thisSum, maxSum;
int maxNum, maxIndex;
int tmpLeft;
int i;

tmpLeft = 0;
thisSum = 0;
maxNum = A[0];
maxIndex = 0;
maxSum = 0;

for (i = 0; i < N; i++) {
if (A[i] > maxNum) {
maxIndex = i;
maxNum = A[i];
}

thisSum += A[i];

if (thisSum > maxSum) {
maxSum = thisSum;
*right = i;
*left = tmpLeft;
}
else if (thisSum < 0) {
thisSum = 0;
tmpLeft = i + 1;
}
}

if (maxNum <= 0) {
*left = maxIndex;
*right = maxIndex;
return maxNum;
}
else {
return maxSum;
}
}

注:当序列中有0的时候,上面几个算法输出的区间并不相同

相关文章:

算法探讨——再议经典算法问题:求最大子序列和、绝对值最大子序列和以及其区间
程序员编程艺术:第七章、求连续子数组的最大和
最大连续子序列和

文章目录
  1. 1. 问题描述
  2. 2. O(n^2)算法
  3. 3. O(nlog(n))算法
  4. 4. O(n)算法
|