题解 | #最大序列和#

#include<cstdio>
using namespace std;

const int MAXN = 1000000;

long long dp[MAXN]; //dp数组 
long long A[MAXN];	//接受输入的值 

int MAX(int a, int b) { //返回两者较大的数 
	if(a > b) {
		return a;
	} else {
		return b;
	}
} 

long long sum(int n) { 		//找出最大连续子序列 
	//1.dp[i]即以i为结尾的连续序列最大和 
	//2.确定递推公式 d[i] = MAX(dp[i-1] + A[i], A[i])
	//3. 初始化
	dp[0] = A[0];
	
	//4.确定递推顺序，从前往后 
	/*5.举例推导递推公式 
		A[] = {1 -2 3 4 -10 6}
		dp[0] = A[0] = 1
		dp[1] = MAX(1 + -2, -2) = -1;
		dp[2] = MAX(-1 + 3, 3) = 3;
		dp[3] = MAX(3 + 4, 4) = 7;
		dp[4] = MAX(7 + -10, -10) = -3;
		dp[5] = MAX(-3 + 6, 6) = 6;
	*/ 
	for (int i = 1; i < n; ++i) {
		dp[i] = MAX(dp[i - 1] + A[i], A[i]);
	}
	long long High = dp[0]; //遍历dp[]找出最大值 
	for(int i = 1; i < n; ++i) {		
		if(dp[i] > High) {
			High = dp[i];
		}
	}
	return High;
}

int main() {
	int n;
	while(scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; ++i) {
			scanf("%lld", &A[i]);
		}
		long long result = sum(n);
		printf("%lld\n", result);
	}
	return 0;
}