i917 - 12640 - Largest Sum Game
題目描述
題目要求找出一個數字序列中，連續數字的最大總和。序列中的數字可以是正數、負數或零。
解題思路
程式碼透過讀取輸入字串，並將其解析為一系列整數。它使用一個迴圈迭代字串，並嘗試提取每個數字。如果遇到負號，則將後續的數字視為負數。程式碼會計算一個累加和，並在每次迭代中更新最大和。如果累加和變為負數，則將其重置為零，因為負數的累加和不會對最大和產生任何貢獻。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入字串的長度。程式碼需要迭代字串一次來解析數字和計算最大和。
- 空間複雜度: O(1)，程式碼只使用幾個整數變數來儲存累加和、最大和和臨時數字，因此空間複雜度是常數。
程式碼
#include <iostream>
using namespace std;
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(getline(cin,s)){
s+=' ';
int ans=0,sum=0;
for(int i=0;i<s.size();++i){
if(s[i]!=' '){
int f=1,tmp=0;
if(s[i]=='-'){
f=-1;
++i;
}
while(s[i]!=' '){
tmp*=10;
tmp+=s[i]-'0';
++i;
}
sum+=tmp*f;
if(sum<0)sum=0;
else ans=max(ans,sum);
}
}
cout << ans << "\n";
}
}