【PAT甲级】1007 Maximum Subsequence Sum (25分)

解题过程的小记录，如有错误欢迎指出。

难度：四星（最大连续子序列和的模板题，第一次写遇上点小坑）

小导航~

• 题目分析
• • • 注意点
• 我的解题过程
• • • 思路
    • bug
    • 代码
• dalao的代码
• • • 借鉴点

题目分析

注意点

我的解题过程

思路

1. 最大子序列和问题，利用dp[j]记录以j结束的最大的子序列和，d[j]=max(d[j-1]+A[i],A[i])
2. 本题和算法笔记中的模板相比较，多出的内容是要记录i的位置，可以用一个pre记录，只有当本身值比前一个dp大时前驱才是自身，否则为前者的前驱

bug

1. 在找dp数组中的最大值时，将第一个值和0比较然后选择较大值，进行赋值再比较，这样会导致有一个测试点不通过，因为本题是有正有负的所以0不算最小值，一定要从dp的第一个值和后面逐渐比较

代码

#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 10005;
int A[MAXN], dp[MAXN], pre[MAXN];

int main()
{
	int k;
	bool flag = false;
	scanf("%d", &k);
	if (k <= 0) {
		return 0;
	}
	for (int i = 0; i < k; i++) {
		scanf("%d", &A[i]);
		if (A[i] >= 0) flag = true;
	}
	if (flag == false) {
		printf("0 %d %d", A[0], A[k - 1]);
		return 0;
	}
	dp[0] = A[0];
	fill(pre, pre + MAXN, 0);
	for (int i = 1; i < k; i++) {
		if (A[i] > A[i] + dp[i - 1]) {
			dp[i] = A[i];
			pre[i] = i;
		}
		else {
			dp[i] = A[i] + dp[i - 1];
			pre[i] = pre[i - 1];
		}
	}
	int maxi = 0, maxj = 0;
	for (int i = 1; i < k; i++) {//找出以i结尾的最大数列和
		if (dp[i] > dp[maxj]) {//***错点，原来设置为和一个初始值为maxnum的进行比较，这样不行，因为有正有负，0不是最小值
			maxj = i;
		}
	}
	maxi = pre[maxj];
	printf("%d %d %d", dp[maxj], A[maxi], A[maxj]);
    return 0;
}
           

dalao的代码

全部代码因版权原因不放出来，大家可以自行去柳神博客购买或者参考晴神的上机笔记~

借鉴点

1. 本题就是参考上机笔记写的