paizaラーニングのレベルアップ問題集「累積和メニュー」からの出典です。
paiza.jp
C++による「累積和メニュー」問題集:【連続するN個の和の最大値】連続するN個の和の最大値4と、それらの提出コードの解答例です。
僕が作成、提出したコードは、以下のとおりです。
・STEP: 1 連続するN個の和の最大値1
/* paizaラーニング: C++による「累積和メニュー」問題集:【連続するN個の和の最大値】連続するN個の和の最大値4 STEP: 1 連続するN個の和の最大値1 https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_step1 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ vector<int> a={1,5,9,7,5,3,2,5,8,4}; vector<int> s(11); s[0]=0; s[1]=a[0]; for(int i=2;i<11;i++){ s[i+1]=s[i]+a[i]; } int ans=-1; for(int i=0;i<=7;i++){ ans=max(ans,s[i+3]-s[i]); } cout<<ans<<endl; return 0; }
・STEP: 2 連続するN個の和の最大値2
/* paizaラーニング: C++による「累積和メニュー」問題集:【連続するN個の和の最大値】連続するN個の和の最大値4 STEP: 2 連続するN個の和の最大値2 https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_step2 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ vector<int> a(10); for(int i=0;i<10;i++){ cin>>a[i]; } vector<int> s(11); s[0]=0; s[1]=a[0]; for(int i=0;i<11;i++){ s[i+1]=s[i]+a[i]; } int ans=-1; for(int i=0;i<=7;i++){ ans=max(ans,s[i+3]-s[i]); } cout<<ans<<endl; return 0; }
・STEP: 3 連続するN個の和の最大値3
/* paizaラーニング: C++による「累積和メニュー」問題集:【連続するN個の和の最大値】連続するN個の和の最大値4 STEP: 3 連続するN個の和の最大値3 https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_step3 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<int> s(n+1); s[0]=0; for(int i=0;i<n;i++){ s[i+1]=s[i]+a[i]; } int ans=-1; for(int i=0;i<=n-3;i++){ ans=max(ans,s[i+3]-s[i]); } cout<<ans<<endl; return 0; }
・FINAL問題:【連続するN個の和の最大値】連続するN個の和の最大値4
/* paizaラーニング: C++による「累積和メニュー」問題集:【連続するN個の和の最大値】連続するN個の和の最大値4 FINAL問題:【連続するN個の和の最大値】連続するN個の和の最大値4 https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_boss 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,k; cin>>n>>k; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<int> s(n+1); s[0]=0; for(int i=0;i<n;i++){ s[i+1]=s[i]+a[i]; } int ans=-1; for(int i=0;i<=n-k;i++){ ans=max(ans,s[i+k]-s[i]); } cout<<ans<<endl; return 0; }
paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。