b565 - 5.採蘑菇攻略問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個整數陣列中，連續子陣列的最大和。輸入包含多組測試案例，每組案例首先給定蘑菇的個數 n，然後給定 n 個整數，代表每個蘑菇的分數。程式需要計算出最佳採法所能獲得的最大分數。

解題思路

本題可以使用 Kadane's Algorithm (連續子陣列最大和問題) 解決。Kadane's Algorithm 是一種動態規劃的應用，其核心思想是：

1. 維護一個當前最大和 ans。
2. 維護一個全局最大和 max。
3. 遍歷陣列，對於每個元素，更新 ans：ans = ans + element。
4. 如果 ans 大於 max，則更新 max。
5. 如果 ans 小於 0，則將 ans 重置為 0，因為負的子陣列和不會對最大和產生貢獻。

這個演算法的關鍵在於，它能夠有效地追蹤到目前為止的最佳子陣列，並在遇到負數時及時重置，從而避免了不必要的計算。

複雜度分析

• 時間複雜度: O(n)，其中 n 是蘑菇的個數。因為我們只需要遍歷陣列一次。
• 空間複雜度: O(1)，因為我們只需要常數級別的額外空間來儲存 ans 和 max。

程式碼

#include <stdio.h>
int main(){
	int a;
	while(scanf("%d",&a)>0){
		int b,ans=0,max=0;
		while(a--){
			scanf("%d",&b);
			ans+=b;
			if(ans>max)max=ans;
			if(ans<0)ans=0;
		}
		printf("%d\n",max);
	}
}