e654 - 10656 - Maximum Sum (II)
題目描述
題目要求從一個非負整數序列中找出總和最大的子序列。如果有多個總和相同的子序列，則選擇長度最短的。如果長度也相同，則選擇序列中數字最先出現的子序列。序列中至少包含一個數字。
解題思路
這題可以使用貪心演算法解決。由於所有數字都是非負的，因此總和最大的子序列必然包含所有非零的數字。程式碼遍歷輸入序列，將所有非零數字輸出，並用空格分隔。如果輸入序列中所有數字都是零，則輸出一個零。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入序列的長度。程式碼需要遍歷輸入序列一次。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n;
while(n=read()){
if(!n)break;
int a;
bool zero=0,first=0;
while(n--){
a=read();
if(a){
if(first)putchar_unlocked(' ');
write(a);
zero=1;
first=1;
}
}
if(!zero){
putchar_unlocked('0');
putchar_unlocked('\n');
}
else
putchar_unlocked('\n');
}
}