leetcode 53の最大連続サブ配列と
2225 ワード
タイトルは整数配列numsを与え、最大和を有する連続サブ配列(サブ配列に少なくとも1つの要素が含まれる)を見つけ、その最大和を返す. 入力:[-2,1,-3,4,-1,2,1,-5,4];出力:6;説明:連続サブ配列[4,−1,2,1]の和は最大で6であった. は,できるだけ複雑度O(n)のアルゴリズムを実現し,分治法も採用できる.
ぶんせきこの問題の最初の考えは直接暴力で解くことだ.三重サイクルですが、時間の複雑さが高すぎます. 分治の方法はアルゴリズムの導論の上で行ったことがあって、配列を2つの部分に分けて、それぞれ最も大きいサブ配列とを求めて、それから1種の2つのサブ配列にまたがる連続配列と、3つの間の最大値を比較します.分治の方法は書くのが面倒です. はネット上の解答を参考にして、動的な計画を利用することができます.重要なのは、ステータスをどのように定義するかです.この問題はi番目の数字を末尾とする最大のサブ配列とdp[i]を定義することができ,i+1番目の数字を末尾とする最大のサブ配列と状態遷移方程式から得ることができる. には、現在の連続配列およびそのサイズに応じて0未満であるか否かを記録する方法もある.0より大きい場合は、後の数値の先頭のサブ配列に前の連続サブ配列を加えるとより大きくなることを証明するので、重ね合わせを続行する必要があります.0より小さい場合は、連続するサブ配列の計算を再開します.スキャンされたサブ配列の最大値を記録する変数を常に保持します.最後に戻って顔を変えればいい.
コード#コード#
第3の方法を採用し,時間が複雑でO(n)と読む.
まとめ
ダイナミックプランニングでは、解の問題を分割し、段階的に解き、中間値を保持する必要があります.
ぶんせき
コード#コード#
第3の方法を採用し,時間が複雑でO(n)と読む.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 。 。
// 0, 。
// ， 。
// ， ， 。
int max = nums[0];
int sum = nums[0];
for(int i = 1; i < nums.size(); i++){
if(sum < 0){
sum = nums[i];
}
else{
sum += nums[i];
}
if(sum > max){
max = sum;
}
}
return max;
}
};まとめ
ダイナミックプランニングでは、解の問題を分割し、段階的に解き、中間値を保持する必要があります.