首页 > 代码库 > 2.14 求数组的子数组之和的最大值

2.14 求数组的子数组之和的最大值

2024-11-16 04:36:02   202人阅读

题目：给定一个一维数组，求这个数组的子数组之和的最大值。


最佳方法：动态规划！


一、
可以将一个大问题（N个元素数组）转化为一个较小的问题（N-1个元素数组）。。
假设已经知道（A[1],...A[n-1]）中最大的子数组的和为：All[1]
并且已经知道（A[1],...A[n-1]）中包括A[1]的子数组的最大和为start[1]


所以最终的解All[0] = max(A[0], A[0]+start[1], All[1])
所以通过DP来求解！


代码如下：

#include <iostream>
#define MAXN 10000

using namespace std;

int A[MAXN], n, start[MAXN], All[MAXN];

int max(int x, int y) {
	return x > y ? x : y;
}

int MaxSum(int *A, int n) {
	start[n - 1] = A[n - 1];
	All[n - 1] = A[n - 1];
	for(int i = n-2; i >= 0; --i) {
		start[i] = max(A[i], start[i + 1] + A[i]);
		All[i] = max(All[i + 1], start[i]);
	}
	return All[0];
}

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	cout << MaxSum(A, n) << endl;
	return 0;
}



二、
上面那种方法时间复杂度为：O(N)，但是空间复杂度不热观。
所以下面寻求空间复杂度为O（1）的算法。


思路：由上面那两个递推式
start[i] = max(A[i], start[i + 1] + A[i]);
All[i] = max(All[i + 1], start[i]);
      可以知道：（1）如果start[i + 1] < 0，那么start[i] = A[i]
（2）start[i + 1]只有在计算start[i]的时候才能用到。
        All[i + 1]只有在计算All[i]的时候才能用到。


所以可以有一种时间复杂度是O(N),而空间复杂度是O(1)的算法。


代码：

#include <iostream>
#define MAXN 10000

using namespace std;

int A[MAXN], n, start[MAXN], All[MAXN];

int max(int x, int y) {
	return x > y ? x : y;
}

int MaxSum(int *A, int n) {
	int nStart = A[n-1];
	int nAll = A[n-1];
	for(int i = n-2; i >= 0; --i) {
		nStart = max(A[i] + nStart, A[i]);
		nAll = max(nStart, nAll);
	}
	return nAll;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	cout << MaxSum(A, n) << endl;
	return 0;
}



三、
当然还有最后一种最简单的写法：

代码：

#include <iostream>
#define MAXN 10000

using namespace std;

int A[MAXN], n, start[MAXN], All[MAXN];

int max(int x, int y) {
	return x > y ? x : y;
}

int MaxSum(int *A, int n) {
	int nStart = A[n-1];
	int nAll = A[n-1];
	for(int i = n-2; i >= 0; --i) {
		if(nStart < 0) nStart = 0;
		nStart += A[i];
		if(nStart > nAll) nAll = nStart;
	}
	return nAll;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	cout << MaxSum(A, n) << endl;
	return 0;
}









2.14 求数组的子数组之和的最大值


联系
我们