【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)
【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)
前言
Problem:1007 Maximum Subsequence Sum (25 分)
Tags:DP
Difficulty:
剧情模式想流点汗想流点血死而无憾Address:1007 Maximum Subsequence Sum (25 分)
问题描述
求最大连续子序列和,输出这个连续子序列的首值、尾值和序列和(优先最靠前的),如果都为这个序列都为负的输出0和整个序列的首尾值。
解题思路
- 一道经典又特殊的动态规划,本身很简单,但考虑到要求最靠前的首尾值,容易出错,难度相应提高。
- dp[i]dp[i]dp[i] 表示以 N[i]N[i]N[i] 为结尾的最大连续子序列和,再用一个 pos[i]pos[i]pos[i] 表示这个子序列的首位置。
- 优化:由于dp访问的单调性,可以压缩空间,用一个dp值和pos值代替这俩个数组。
参考代码
1. 未压缩空间:
#include<iostream>
#include<vector>using namespace std;
int K; // K integers 1e4
vector<int> N;
vector<int> dp, start_index;
int maxi;void init() {cin >> K;N.resize(K, 0);dp.resize(K, 0);start_index.resize(K, 0);for (int i = 0; i < K; ++i) {cin >> N[i];}}void do_dp() {maxi = 0;dp[0] = N[0];start_index[0] = 0;for (int i = 1; i < K; i++) {if (dp[i - 1] >= 0) {dp[i] = dp[i - 1] + N[i];start_index[i] = start_index[i - 1];} else {dp[i] = N[i];start_index[i] = i;}maxi = dp[i] > dp[maxi] ? i : maxi;}
}void solution_1007() {init();do_dp();if (dp[maxi] < 0) {cout << 0 << " " << N[0] << " " << N[K - 1] << endl;return;}cout << dp[maxi] << " " << N[start_index[maxi]] << " " << N[maxi] << endl;
}
int main() {solution_1007();return 0;
}
2. 压缩空间:
(参考柳神 https://github.com/liuchuo/PAT/tree/master/AdvancedLevel_C++ )
这么写后竟然奇妙的发现当所有值都是负的时 leftindex 、rightindex会保持初始值,总而言之精简了很多,膜拜 orz。
#include<iostream>
#include<vector>using namespace std;
int K; // K integers 1e4
vector<int> N;
int dp, temp_start_index, left_index, right_index;
int maxx;void init() {cin >> K;N.resize(K, 0);for (int i = 0; i < K; ++i) {cin >> N[i];}}
void do_dp() {maxx = -1;dp = 0;temp_start_index = 0;left_index = 0;right_index = K - 1;for (int i = 0; i < K; i++) {// 注意从上一个循环继承来的 dp 值永远不会小于0,给原 dp 值加上 N[i] 后再判断dp = dp + N[i];if (dp < 0) { // 加上 N[i] 后 dp 小于0了,只可能因为 N[i] 为负数dp = 0;temp_start_index = i + 1;} else if (dp > maxx) { // 获得更大子串和maxx = dp;left_index = temp_start_index;right_index = i;}}
}void solution_1007() {init();do_dp();if (maxx < 0) {maxx = 0;}cout << maxx << " " << N[left_index] << " " << N[right_index] << endl;
}
int main() {solution_1007();return 0;
}
总结
对于这种会保存下标的题,coding时不要分心写错了,一开始把 pos_start[i] = i
写成了 pos_start[i] = N[i]
,由于样例能过检查了好久才找出来(情人节不适合code)。