1007.md

1007

• 1007 Maximum Subsequence Sum (25 point(s))
• Maximum Subsequence Sum

O(n)

#include <iostream>
#include <algorithm>
using namespace std;

int N;
const int MAX_N = 1e5 + 5;
int A[MAX_N], dp[MAX_N];
int start[MAX_N];

int main() {
	bool is_all_negative = true;
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> A[n];
		if (A[n] >= 0) {
			is_all_negative = false;
		}
	}
	if (is_all_negative) {
		cout << "0 " << A[0] << " " << A[N - 1] << endl;
	}
	else {
		dp[0] = A[0];
		for (int i = 1; i < N; i++) {
			if (dp[i - 1] + A[i] >= A[i]) {
				dp[i] = dp[i - 1] + A[i];
				start[i] = start[i - 1];
			}
			else {
				dp[i] = A[i];
				start[i] = i;
			}
		}
		int max_index = max_element(dp, dp + N) - dp;
		cout << dp[max_index] << " " << A[start[max_index]] << " " << A[max_index] << endl;
	}
	return 0;
}

/*
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4

Sample Input:
6
-2 11 -4 13 -5 -2
Sample Output:
20 11 13
*/

O(n^2)

#include <iostream>
using namespace std;

int K;	// 1 <= K <= 10000
const int MAX_K = 1e4 + 5;
int arr[MAX_K], sum[MAX_K] = { 0 };	// sum[2] = arr[0] + arr[1];

int main() {
	bool all_negative = true;
	cin >> K;
	for (int k = 0; k < K; k++) {
		cin >> arr[k];
		if (arr[k] >= 0) {
			all_negative = false;
		}
		sum[k + 1] = sum[k] + arr[k];
	}
	if (all_negative) {
		cout << "0 " << arr[0] << " " << arr[K - 1] << endl;
	}
	else {
		int MAX = -1, start = -1, end = -1;
		for (int i = 0; i <= K; i++) {
			for (int j = i + 1; j <= K; j++) {
				if (sum[j] - sum[i] > MAX) {
					start = i;
					end = j;
					MAX = sum[j] - sum[i];
				}
			}
		}
		cout << MAX << " " << arr[start] << " " << arr[end - 1] << endl;
	}
	return 0;
}

/*
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4

Sample Input:
6
-2 11 -4 13 -5 -2
Sample Output:
20 11 13
*/

References

• 算法笔记