【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. 本題就是參考上機筆記寫的