e166 - 演唱會記行 - 粉絲應援
題目描述
題目描述了演唱會的應援活動，粉絲們希望製造最大的波浪。給定一排座位上每個粉絲的波浪值，要求計算最大的連續波浪高度。由於場地是圓形的，因此需要將數組拼接起來考慮。
解題思路
本題的核心是找到數組中最大子數列和。由於場地是圓形的，因此需要將數組拼接成一個環形數組，然後找到環形數組的最大子數列和。 程式碼中，首先將數組複製一份，形成一個長度為 2n 的數組，模擬環形結構。然後，使用 Kadane's Algorithm 尋找最大子數列和。Kadane's Algorithm 是一種動態規劃算法，用於在 O(n) 時間內找到數組的最大子數列和。 如果數組中沒有負數，則最大波浪高度為所有元素的總和。如果存在負數，則使用 Kadane's Algorithm 尋找最大子數列和。 最後，如果最大子數列和為負數，則取其絕對值。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#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 max(const int &x,const int &y) { return (((y-x)>>(32-1))&(x^y))^y; }
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
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()){
int a[n+n+1]={0},ma=-10000,s=0,tmp;
for(int i=0;i<n;++i){
a[i]=read();
a[n+i]=a[i];
if(a[i]<0)s=1;
}
if(s){
for(int i=0,in=n;i<n;++i,++in){
if(a[i]<0){
tmp=0;
for(int j=i;j<in;++j){
tmp=max(a[j],tmp+a[j]);
ma=max(tmp,ma);
}
}
}
}
else{
ma=0;
for(int i=0;i<n;++i)
ma+=a[i];
}
if(ma<0){
ma*=-1;
putchar_unlocked('-');
}
write(ma);
putchar_unlocked('\n');
}
}