a540 - 10684 - The jackpot

🔗 前往 ZeroJudge 原題

題目描述

題目要求在一串賭局的盈虧金額中，找出連續賭局的最大總盈餘。輸入包含多組測試案例，每組案例以一個正整數 N 表示賭局數量，後續 N 個整數代表每局的盈虧金額。當 N 為 0 時，表示輸入結束。如果所有賭局都無法盈利，則輸出 "Losing streak."，否則輸出最大連續盈利金額。

解題思路

本題可以使用 Kadane's Algorithm (連續最大和) 解決。Kadane's Algorithm 是一種動態規劃的應用，用於尋找數組中連續子數組的最大和。

演算法的核心思想是：

1. 維護一個 max_so_far 變數，用於記錄到目前為止找到的最大和。
2. 維護一個 current_max 變數，用於記錄以當前元素結尾的連續子數組的最大和。
3. 遍歷數組，對於每個元素，更新 current_max 為 current_max + element 和 element 中的較大值。
4. 更新 max_so_far 為 max_so_far 和 current_max 中的較大值。

在程式碼中，max 變數對應 max_so_far，now 變數對應 current_max。如果 now 變為負數，則重置為 0，因為負數的連續子數組不可能帶來更大的和。

複雜度分析

• 時間複雜度: O(n)，其中 n 是賭局的數量。因為程式碼只需要遍歷一次輸入數列。
• 空間複雜度: O(1)，因為程式碼只使用了幾個常數大小的變數。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,b;
	while(cin >> a){
		if(a==0)break;
		int max=0,now=0;
		while(a--){
			cin >> b;
			now+=b;
			if(now<0)
				now=0;
			else if(now>max)
				max=now;	
		}
		if(max==0)
			cout << "Losing streak.\n";
		else
			cout << "The maximum winning streak is " << max << ".\n";	
	}
}