動的計画の正体を暴露する--アルゴリズム第3章のオンライン実践報告
2453 ワード
アルゴリズム第三章オンライン実践報告
一、実践テーマ
7-2最大サブセグメント和(40分)
n個の整数(負数である可能性がある)からなるシーケンスa[1],a[2],a[3],...,a[n]を与え、このシーケンス、例えばa[i]+a[i+1]+...+a[j]のサブセグメント和の最大値を求める.与えられた整数が負の場合、サブセグメントと0を定義します.
要求アルゴリズムの時間的複雑度はO(n)である.
入力形式:
2行入力:
1行目はn値(1<=n<=10000)である.
2行目はn個の整数です.
出力フォーマット:
最大サブセグメント和を出力します.
サンプルを入力:
ここに入力のセットを示します.例:
出力サンプル:
ここでは、対応する出力が与えられます.例:
二、問題の説明
次に入力する配列要素の個数を表す数を入力し、2行目にすべての要素を入力し、最大サブセグメントと(負の数であれば0を出力します)を求めます.
すなわち、最初の数から後に数を加算し、正の数であればこのサブセグメントが「有用」であることを示し、逆に「最大サブセグメントに寄与しない」ことを示す.最後の数を末尾と前の数の末尾のそれぞれの大きさを判断し、大きいものを取って、1つの記録用の変数に再帰的に付与すればよい.
三、アルゴリズムの説明
1、動的計画
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
最初の数字から、dp配列と記録用の変数maxnに初期値0を付与し、dp[i]をi番目の数字で終わる最大サブセグメント和とする.毎回dp[i]は配列のi番目の数とdp[i-1]を取って現在指向しているこの数の中で大きいものを加えます(意味は、現在指向している数がdp[i-1]に現在指向しているこの数を加えても大きい場合、前のサブセグメントと負の数を説明して、寄与していない場合は取りません).「maxn=max(maxn,dp[i])」は負の数をフィルタリングし、正であれば最大のサブセグメントと(dp配列はそれぞれの数で終わる最大サブセグメントと)をとる.
2、判定出力
if(maxn) cout<
else cout<<0<
maxnが正数であれば最大サブセグメントと出力が得られ、そうでなければ(maxnは0または負数)、配列はすべて負数または最大サブセグメントと0であり、要求に応じて0が出力される.
3、完全なコード
#include
#include
using namespace std;
int n,maxn;
int a[10005],dp[10005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
if(maxn) cout<
else cout<<0<
return 0;
}
四、アルゴリズム時間及び空間複雑度分析
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
ループ再帰的にn回呼び出され、動的計画問題の一般的な時間複雑度はO(n)またはO(n^2)であり、明らかにここではO(n)である.
この問題を解くには,dp配列とmaxn変数を補助として用い,空間複雑度は同様にO(n)である.
五、心得
問題の鍵をつかんで、問題の構想を整理して、1本の“難しいです”のテーマに見えます実はとても“簡単です”.特にダイナミックプランニングの問題は,絶えずダイナミックに下から上へ新しい要素を追加して結果を得,最後に問題を解決する.
考えが思いついたが、时にはどのようにコードを叩くか分からないことがあり、自分の問題の数が少なすぎて、コードを打つ時間と回数が少なすぎて、まだ空想の段階にとどまっていることを反映して、これは大きな問題で、早急に修正して向上しなければならない.
チームメイトはとても強くて、时にはチームメイトに依存することがあります.まず自分で考えてからチームメイトと討論してこそ、向上することができます.
一、実践テーマ
7-2最大サブセグメント和(40分)
n個の整数(負数である可能性がある)からなるシーケンスa[1],a[2],a[3],...,a[n]を与え、このシーケンス、例えばa[i]+a[i+1]+...+a[j]のサブセグメント和の最大値を求める.与えられた整数が負の場合、サブセグメントと0を定義します.
要求アルゴリズムの時間的複雑度はO(n)である.
入力形式:
2行入力:
1行目はn値(1<=n<=10000)である.
2行目はn個の整数です.
出力フォーマット:
最大サブセグメント和を出力します.
サンプルを入力:
ここに入力のセットを示します.例:
6-2 11 -4 13 -5 -2出力サンプル:
ここでは、対応する出力が与えられます.例:
20二、問題の説明
次に入力する配列要素の個数を表す数を入力し、2行目にすべての要素を入力し、最大サブセグメントと(負の数であれば0を出力します)を求めます.
すなわち、最初の数から後に数を加算し、正の数であればこのサブセグメントが「有用」であることを示し、逆に「最大サブセグメントに寄与しない」ことを示す.最後の数を末尾と前の数の末尾のそれぞれの大きさを判断し、大きいものを取って、1つの記録用の変数に再帰的に付与すればよい.
三、アルゴリズムの説明
1、動的計画
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
最初の数字から、dp配列と記録用の変数maxnに初期値0を付与し、dp[i]をi番目の数字で終わる最大サブセグメント和とする.毎回dp[i]は配列のi番目の数とdp[i-1]を取って現在指向しているこの数の中で大きいものを加えます(意味は、現在指向している数がdp[i-1]に現在指向しているこの数を加えても大きい場合、前のサブセグメントと負の数を説明して、寄与していない場合は取りません).「maxn=max(maxn,dp[i])」は負の数をフィルタリングし、正であれば最大のサブセグメントと(dp配列はそれぞれの数で終わる最大サブセグメントと)をとる.
2、判定出力
if(maxn) cout<
else cout<<0<
maxnが正数であれば最大サブセグメントと出力が得られ、そうでなければ(maxnは0または負数)、配列はすべて負数または最大サブセグメントと0であり、要求に応じて0が出力される.
3、完全なコード
#include
#include
using namespace std;
int n,maxn;
int a[10005],dp[10005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
if(maxn) cout<
else cout<<0<
return 0;
}
四、アルゴリズム時間及び空間複雑度分析
for(int i=1;i<=n;i++){
dp[i]=max(a[i],dp[i-1]+a[i]);
maxn=max(maxn,dp[i]);
}
ループ再帰的にn回呼び出され、動的計画問題の一般的な時間複雑度はO(n)またはO(n^2)であり、明らかにここではO(n)である.
この問題を解くには,dp配列とmaxn変数を補助として用い,空間複雑度は同様にO(n)である.
五、心得
問題の鍵をつかんで、問題の構想を整理して、1本の“難しいです”のテーマに見えます実はとても“簡単です”.特にダイナミックプランニングの問題は,絶えずダイナミックに下から上へ新しい要素を追加して結果を得,最後に問題を解決する.
考えが思いついたが、时にはどのようにコードを叩くか分からないことがあり、自分の問題の数が少なすぎて、コードを打つ時間と回数が少なすぎて、まだ空想の段階にとどまっていることを反映して、これは大きな問題で、早急に修正して向上しなければならない.
チームメイトはとても強くて、时にはチームメイトに依存することがあります.まず自分で考えてからチームメイトと討論してこそ、向上することができます.