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

代码如下：

#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;
}

#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 求数组的子数组之和的最大值

原文：http://blog.csdn.net/u010470972/article/details/43112953