最大子串和(Maximun-sum)

发表于   |  

前言

本周的专题是maximum sum，即求最大子串和，或最大子数组和。（下文称最大子串和）
题意是：给出一串数, 范围是N, 在若干个子串中，求出子串之和最大的那一个。
如0，-2，3，5，-1，2， 最大子串和是9, 由3，5，-1，2得到。

这类问题在编程之美以及各类笔试题中有出现，网上对这类问题的解法多且杂。
现归纳如下：

一维数组

通常我们假定求出的最大子串和为正数， 即以下算法不考虑最大子串和为负数的情况。
想了解最优算法请直接跳到问题一的解法四。

问题一

简单的一维数组，仅要求给出最大子串和。

解法一

枚举每一个子串，计算和，找出其中最大，运行时间 O(N^3)
i,j 为子串首尾的下标, 暴力枚举每一个子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int MaxSubSum(int A[], int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;
            
            for (int k = i; k <= j; k++)
                sum += A[k];
                
            if (sum > max)
                max = sum;
        }
    }
    return max;
}

解法二

解法一需要三重循环， 然而这就出现了大量不必要的计算， 稍加改进就可以得到 O(N^2) 的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubSum(int A[], int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += A[j];
                        
            if (sum > max)
                max = sum;
        }
    }
    return max;
}

解法三

分治思想，我们吧问题分为两个大致相等的子问题，然后递归地对他们进行求解。
然后将两个子问题的解合并到一起再进行少量的附加共组，最后得到整个问题的解。
设一个二维数组m，其中m[i][j] (i<=j)为A[i]，...,A[j]这个串的最大子串和
可得到递归表达式为m[0][n-1] = max{m[0][n/2-1], m[n/2][n-1], m[0][n-1]}
即，最大子串要么在串的前半部分，要么在串的后半部分，要么横跨这两个部分。
该算法的运行时间为 O(NlogN)

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
int maxSumRec(int A[], int left, int right) {
    if (left == right)  // Base case
        if (A[left] > 0)
            return A[left];
        else
            return 0;
    
    int center = (left + right) / 2;
    int maxLeftSum = maxSumRec(A, left, center);
    int maxRightSum = maxSumRec(A, center + 1, right);
    
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= left; i--) {
        leftBorderSum += A[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++) {
        rightBorderSum += A[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    
    return max(max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);
}

// Test
int ans = maxSumRec(A, 0, n-1);

解法四

Kadane 提出的解决方法，基于动态规划，也是运行时间最快的，只需 O(N)

1
2
3
4
5
6
7
//from wiki
def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSum(int A[], int n) {
    int max = 0, sum = 0;
    
    for (int j = 0; j < n; j++) {
        sum += A[j];

        if (sum > max) {
            max = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }
    return max;
}

正确性分析（摘自《数据结构与算法分析-Java语言描述》）：
像解法一和解法二一样，j代表当前序列的终点，而i代表当前序列的起点。
碰巧的是，我们不知道最佳的子序列在哪里，那么i的使用可以脱离程序进行优化，
因此在设计算法的时候假设i是需要的，而且我们想要改进解法二。
一个结论是，如果A[i]是负的，那么它不可能代表最优子序列的起点，因为任何包含A[i]作为起点的子序列有可以用A[i+1]作为起点从而得到改进。类似的，任何负的子序列不可能是最优子序列的前缀。
如果在内循环中检测到从A[i]到A[j]的子序列是负的，那么我们可以推进i。关键的结论是，我们不仅可以把i推进到i+1,而且实际上还可以把它一直推进到j+1。
为了看清楚这一点，令p为i+1和j之间的任意下标。开始于下标p的任意子序列都不大于 开始于i并包含从A[i]到A[p-1]的子序列的对应子序列，因为后面的子序列不是负的（j是从下标i开始的子序列为负的第一个下标）。
因此，把i推进到j+1是没有风险的：我们不能错过一个最优解。

解法五

在网上看到的，时间复杂度也是 O(N)
设B[i] 为 A[0],…,A[i]的串
最大子串和为： max{(0 <= j < i <= n-1)|B[i]-B[j]}

1
2
3
4
5
6
7
8
9
10
int MaxSum(int* A, int n) {
	int _max = -INF;
	int _min = 0 ,sum = 0;
	for (int i = 0; i < n; i++) {
		sum += A[i];
		_max = max(ans, sum-_min);
		_min = min(sum, _min);
	}
	return _max;
}

问题二

简单的一维数组，不仅要求给出最大子串和，还有该子串的位置，用两个变量表示下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int MaxSum(int* A, int n， int* left, int* right) {
    int max = -INF;
    int cursum = 0, ll = 0;
    left = right = 0;
    for (int i = 0; i < n; i++) {
        if (cursum < 0) {
            cursum = A[i]
            tmpl = i;     //tmpl 临时记录子串的起始下标
        } else {
            cursum += A[i]
        }
        if (cursum > max) {
            max = cursum;
            left = tmpl;
            right = i;
        }
    }
    return max;
}

二维数组

题目：给出一个N*M的二维数组，求出子数组中的最大和。

解法一

暴力枚举，计算求和比较，时间复杂度至少为 O(N^2*M^2)

解法二

将其转化为若干个一位数组，将问题化归。
我们将 N行M列的数组 转化为 长度为M的数组， 即同一列的数之和可以转化为一个数
这样我们可得到 N * (N+1) / 2 个一维数组，这个问题上文已有解法。
时间复杂度为(N * M * min(N,M))

练习

Problem A : The jackpot

From:UVA, 10684
该问题的直接应用

Problem B : Jill Rides Again

From:UVA, 507
本题注意题目给出的条件：子串和相等时取长度大的，长度相同时，取起点最小的。
所以修改max的判断条件改为 if (cursum > max || cursum == max && i-tmpl>right-left) …

Problem C : Maximum Sum

From:UVA, 108
给出一个N*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
int [][][] block;
/* The meaning of three-dimensional array block:
 * 		k
 * -------------	i
 * |  |  |  |  |
 * -------------
 * |  |  |  |  |
 * -------------	j
 * |  |  |  |  |
 * -------------
 * block[i][j][k] --> 原矩阵 第i行到第j行 第k列 组成的 (j-i)×1 的子矩阵
 */

void initBlock(int **A, int n) {
	int [] tsum;
	block = new int [n][n][n];
	for (int k = 0; k < n; k++) {
		tsum = new int [n];
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				tsum[i] = A[0][k];
			} else {
				tsum[i] = tsum[i-1] + A[i][k];
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (i == 0) {
					block[i][j][k] = tsum[j];
				} else {
					block[i][j][k] = tsum[j] - tsum[i-1];
				}
			}
		}
	}
}

int MaxSum(int*** block, int n) {
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			// now three-dimensional array changed to linear array
			int sum = 0;
			for (int k = 0; k < n; k++) {	
				if (sum < 0) {
					sum = block[i][j][k];
				} else {
					sum += block[i][j][k];
				}
				if (sum > max) {
					max = sum;
				}
			}
		}
	}
	return max;
}

##参考
Maximum subarray problem
最大子数组和（最大子序列和 | 连续子数组最大和）
连续子串的最大值(经典的DP问题)
最大子串和问题（Maximum Subarray）
面试题31：连续子数组的最大和