求给定N个整数的序列{A1,A2,……,An},求函数 f(i,j)=max{0,∑(i→j)Ak}的最大值

算法1

直接暴力求出每个子序列和的值,然后取最大的值。时间复杂度为O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int MaxSubseqSum1(int A[], int N)
{
int ThisSum, MaxSum = 0;
int i, j, k;

for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
ThisSum = 0;
for (k = i; k <= j; k++)
ThisSum += A[k];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;//更新最大值
}
}
}
return MaxSum;
}



算法2

在算法1的基础上进行优化,时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int MaxSubseqSum2(int A[], int N)
{
int ThisSum, MaxSum = 0;
int i, j;

for (i = 0; i < N; i++) {
ThisSum = 0;
for (j = i; j < N; j++) {
ThisSum += A[j];
}
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
}
}
return MaxSum;
}



算法3:分而治之处理

==时间复杂度为O(n^2)的可以想办法优化成O(n㏒n)==
递归分成两份,分别求每个分割后最大子列和,时间复杂度为 O(n*logn)

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
/* 返回三者中最大值*/
int Max3(int A, int B, int C) {
return (A > B) ? ((A > C) ? A : C) : ((B > C) ? B : C);
}
/* 分治*/
int DivideAndConquer(int a[], int left, int right) {

/*递归结束条件:子列只有一个数字*/
// 当该数为正数时,最大子列和为其本身
// 当该数为负数时,最大子列和为 0
if (left == right) {
if (0 < a[left])
return a[left];
return 0;
}

/* 分别递归找到左右最大子列和*/
int center = (left + right) / 2;
int MaxLeftSum = DivideAndConquer(a, left, center);
int MaxRightSum = DivideAndConquer(a, center + 1, right);

/* 再分别找左右跨界最大子列和*/
int MaxLeftBorderSum = 0;
int LeftBorderSum = 0;
for (int i = center; i >= left; i--) { //应该从边界出发向左边找
LeftBorderSum += a[i];
if (MaxLeftBorderSum < LeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
int MaXRightBorderSum = 0;
int RightBorderSum = 0;
for (int i = center + 1; i <= right; i++) { // 从边界出发向右边找
RightBorderSum += a[i];
if (MaXRightBorderSum < RightBorderSum)
MaXRightBorderSum = RightBorderSum;
}

/*最后返回分解的左边最大子列和,右边最大子列和,和跨界最大子列和三者中最大的数*/
return Max3(MaxLeftSum, MaxRightSum, MaXRightBorderSum + MaxLeftBorderSum);
}
int MaxSubseqSum3(int a[], int n) {
return DivideAndConquer(a, 0, n - 1);
}



算法4:在线处理

“贪心法”,即不从整体最优上加以考虑,只做出某种意义上的局部最优解。
其实最大子列和与它的首部和尾部都没有关系,我们只关心它当前的大小。
当临时和加上当前值为负时,它对之后子列和肯定没有帮助(甚至只会让之后的和更小!),
我们抛弃这段临时和将它置0。时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubseqSum4(int A[], int N)
{
int ThisSum = 0, MaxSum = 0;
int i;
for (i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}

评论