最大連続サブセグメント和
6541 ワード
/********************************************************************
アルゴリズム4は、最大連続サブセグメント和の開始位置と終了位置を記録することができ、原文に誤りがあるかどうか分からない.
コード:
ネット上の多くの他のネットユーザーの解答はすべてはっきり説明していないで、最も大きいサブシーケンスと一定は連続していて、もし連続しなければ、意味がありません.私たちは配列をスキャンして、その中のすべての正の整数を出力すればいいので、彼らの和はきっと最大です.
前にもう一つの問題があって、最長の増分子のシーケンスを求めて、この子のシーケンスは連続しなくてもいいです.彼らが記述した状態変換方程式に現れる.
問題の説明:
整数のセットを入力し、このセットの数値のサブシーケンスと最大値を求めます.つまり,最も大きなサブシーケンスの和を求める限り,最大のそのシーケンスを求める必要はない.例:
シーケンス:-211-413-5-2で、最も大きいサブシーケンスと20です.
シーケンス:-62 4-7 5 3 2-16-90-2の場合、最も大きなサブシーケンスとは16です.
アルゴリズム1:
//窮挙法、複雑度O(n^3)
long maxSubSum1(const vector& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
これはO(N^3)のアルゴリズムで、アルゴリズム自体が分かりやすく、直感的な感覚で無駄な操作をたくさんしました.例えば、i=0、j=3の場合、a[0]+a[1]+...+a[3]が計算される.一方、i=0、j=4の場合、a[0]+a[1]+...a[4]も計算される.
アルゴリズム2:
forサイクルを1つ取り除くことで3回の時間を避ける.
//窮挙法ですが、上記の不要な操作Oを減らしました(n^2)
long maxSubSum2(const vector& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
これは非常に直観的な貧挙法(上の解析よりも簡単)であり,余分な繰返し操作がなく,複雑度はO(N^2)である.ここで、thisSumはa[i]+a[i+1]+...+a[j-1]を表す.
アルゴリズム3:
この問題に対して,再帰を用いる比較的複雑なO(Nlogn)の解法がある.もしシーケンスの位置を求めるならば、これは最も良いアルゴリズムになります(私たちの後にO(N)のアルゴリズムがまだあるので、しかし最も大きいサブシーケンスの位置を求めることができません).この方法は「分治戦略」(divide-and-conquer)を用いる.
我々の例では、最も大きなサブシーケンスが3つの場所で現れるか、左半分、または右半分、または入力データの中部を越えて左右の2つの部分を占める可能性がある.前の2つのケースを再帰的に解き,第3のケースの最大和は,前半の最大和(前半の最後の要素を含む)と後半の最大和(後半の最初の要素を含む)を加算することによって得ることができる.
//再帰法、複雑度はO(nlogn)
long maxSumRec(const vector& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right)/2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//左対後の数字で終わるシーケンスの最大値を求める
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//右対後の数字で終わるシーケンスの最大値を求める
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector& a)
{
return maxSumRec(a, 0, a.size()-1);
}
またmax 3(long,long,long)は、3つのlongの最大値を求めることを表す.
//3つのlongの最大値を求める
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
このアルゴリズムを分析します.
T(1) = 1
T(N) = 2T(N/2) + O(N)
最後に,アルゴリズムの複雑さはO(Nlogn)であった.
アルゴリズム4:
次に、多くの賢いアルゴリズムの典型である線形アルゴリズムを紹介します.このアルゴリズムは、実行時間は明らかですが、正確性は明らかではありません(理解しにくい).
//線形アルゴリズムO(N)
long maxSubSum4(const vector& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
時間界O(N)が正しいのは分かりやすいが、なぜ正しいのかを理解するのは骨が折れる.実はこれはアルゴリズム2の改善です.解析の場合もiは現在のシーケンスの始点を表し,jは現在のシーケンスの終点を表す.最適なサブシーケンスの位置を知る必要がなければ,iは最適化できる.
ポイントの1つの考え方は、a[i]が負数であれば、最もシーケンスのある起点を表すことはできない.a[i]を含む起点となるサブシーケンスは、a[i+1]を起点として改善することができるからである.同様に、任意の負のサブシーケンスが最適なサブシーケンスのプレフィックスであることは不可能である.例えば,ループではa[i]からa[j]までのサブシーケンスが負であることを検出し,iを進めることができる.重要な結論は,iをi+1に推進できるだけでなく,実際にj+1に推進できることである.
例えば、pをi+1~jのいずれかの下付き文字とし、a[i]+…+a[j]が負であると仮定したため、下付き文字pに始まる任意のサブシーケンスは、下付き文字iよりも大きくなく、a[i]~a[p-1]のサブシーケンスに対応するサブシーケンスを含む(jは、下付き文字iから負の数となる最初の下付き文字である).したがって,iをj+1に進めることは安全であり,最適解を逃すことはない.なお、a[j]で終わるシーケンスと負の数がある場合は、このシーケンスのいずれかの数がa[j]の後の数と形成される最大子シーケンスの先頭であることは不可能であることを示しているが、a[j]の前のシーケンスが最大シーケンスではないことを示していない.すなわち、最大子シーケンスがa[j]の前であるかa[j]の後であるかを確定できないということである.すなわち、最も大きなサブシーケンス位置は求められない.ただし、maxSumの値が現在最大のサブシーケンス和であることを確認できます.このアルゴリズムのもう一つの点は,データを1回だけスキャンし,a[j]が読み込まれると再記憶する必要がないことである.オンラインアルゴリズムです.
オンラインアルゴリズム:任意の時点でアルゴリズムは、読み込まれたデータに対して現在のデータの解を与えることができます.
定数空間線形時間のオンラインアルゴリズムはほとんど完璧なアルゴリズムである.
アルゴリズム4は、最大連続サブセグメント和の開始位置と終了位置を記録することができ、原文に誤りがあるかどうか分からない.
コード:
#include
#include
using namespace std;
const int maxn = 1000005;
int main(void)
{
int n, t;
scanf("%d", &t);
while(t--)
{
int s = 0, S = 0, E = 0;
scanf("%d", &n);
long long x, ans = 0, temp = 0;
for(int i = 0; i < n; i++)
{
scanf("%lld", &x);
temp += x;
if(temp <= 0) { temp = 0; s = i+1; }
if(temp > ans) { ans = temp; S = s; E = i; }
}
printf(" ： %d
: %d
", S+1, E+1);
printf("%lld
", ans);
}
return 0;
} ネット上の多くの他のネットユーザーの解答はすべてはっきり説明していないで、最も大きいサブシーケンスと一定は連続していて、もし連続しなければ、意味がありません.私たちは配列をスキャンして、その中のすべての正の整数を出力すればいいので、彼らの和はきっと最大です.
前にもう一つの問題があって、最長の増分子のシーケンスを求めて、この子のシーケンスは連続しなくてもいいです.彼らが記述した状態変換方程式に現れる.
問題の説明:
整数のセットを入力し、このセットの数値のサブシーケンスと最大値を求めます.つまり,最も大きなサブシーケンスの和を求める限り,最大のそのシーケンスを求める必要はない.例:
シーケンス:-211-413-5-2で、最も大きいサブシーケンスと20です.
シーケンス:-62 4-7 5 3 2-16-90-2の場合、最も大きなサブシーケンスとは16です.
アルゴリズム1:
//窮挙法、複雑度O(n^3)
long maxSubSum1(const vector
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
これはO(N^3)のアルゴリズムで、アルゴリズム自体が分かりやすく、直感的な感覚で無駄な操作をたくさんしました.例えば、i=0、j=3の場合、a[0]+a[1]+...+a[3]が計算される.一方、i=0、j=4の場合、a[0]+a[1]+...a[4]も計算される.
アルゴリズム2:
forサイクルを1つ取り除くことで3回の時間を避ける.
//窮挙法ですが、上記の不要な操作Oを減らしました(n^2)
long maxSubSum2(const vector
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
これは非常に直観的な貧挙法(上の解析よりも簡単)であり,余分な繰返し操作がなく,複雑度はO(N^2)である.ここで、thisSumはa[i]+a[i+1]+...+a[j-1]を表す.
アルゴリズム3:
この問題に対して,再帰を用いる比較的複雑なO(Nlogn)の解法がある.もしシーケンスの位置を求めるならば、これは最も良いアルゴリズムになります(私たちの後にO(N)のアルゴリズムがまだあるので、しかし最も大きいサブシーケンスの位置を求めることができません).この方法は「分治戦略」(divide-and-conquer)を用いる.
我々の例では、最も大きなサブシーケンスが3つの場所で現れるか、左半分、または右半分、または入力データの中部を越えて左右の2つの部分を占める可能性がある.前の2つのケースを再帰的に解き,第3のケースの最大和は,前半の最大和(前半の最後の要素を含む)と後半の最大和(後半の最初の要素を含む)を加算することによって得ることができる.
//再帰法、複雑度はO(nlogn)
long maxSumRec(const vector
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right)/2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//左対後の数字で終わるシーケンスの最大値を求める
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//右対後の数字で終わるシーケンスの最大値を求める
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector
{
return maxSumRec(a, 0, a.size()-1);
}
またmax 3(long,long,long)は、3つのlongの最大値を求めることを表す.
//3つのlongの最大値を求める
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
このアルゴリズムを分析します.
T(1) = 1
T(N) = 2T(N/2) + O(N)
最後に,アルゴリズムの複雑さはO(Nlogn)であった.
アルゴリズム4:
次に、多くの賢いアルゴリズムの典型である線形アルゴリズムを紹介します.このアルゴリズムは、実行時間は明らかですが、正確性は明らかではありません(理解しにくい).
//線形アルゴリズムO(N)
long maxSubSum4(const vector
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
時間界O(N)が正しいのは分かりやすいが、なぜ正しいのかを理解するのは骨が折れる.実はこれはアルゴリズム2の改善です.解析の場合もiは現在のシーケンスの始点を表し,jは現在のシーケンスの終点を表す.最適なサブシーケンスの位置を知る必要がなければ,iは最適化できる.
ポイントの1つの考え方は、a[i]が負数であれば、最もシーケンスのある起点を表すことはできない.a[i]を含む起点となるサブシーケンスは、a[i+1]を起点として改善することができるからである.同様に、任意の負のサブシーケンスが最適なサブシーケンスのプレフィックスであることは不可能である.例えば,ループではa[i]からa[j]までのサブシーケンスが負であることを検出し,iを進めることができる.重要な結論は,iをi+1に推進できるだけでなく,実際にj+1に推進できることである.
例えば、pをi+1~jのいずれかの下付き文字とし、a[i]+…+a[j]が負であると仮定したため、下付き文字pに始まる任意のサブシーケンスは、下付き文字iよりも大きくなく、a[i]~a[p-1]のサブシーケンスに対応するサブシーケンスを含む(jは、下付き文字iから負の数となる最初の下付き文字である).したがって,iをj+1に進めることは安全であり,最適解を逃すことはない.なお、a[j]で終わるシーケンスと負の数がある場合は、このシーケンスのいずれかの数がa[j]の後の数と形成される最大子シーケンスの先頭であることは不可能であることを示しているが、a[j]の前のシーケンスが最大シーケンスではないことを示していない.すなわち、最大子シーケンスがa[j]の前であるかa[j]の後であるかを確定できないということである.すなわち、最も大きなサブシーケンス位置は求められない.ただし、maxSumの値が現在最大のサブシーケンス和であることを確認できます.このアルゴリズムのもう一つの点は,データを1回だけスキャンし,a[j]が読み込まれると再記憶する必要がないことである.オンラインアルゴリズムです.
オンラインアルゴリズム:任意の時点でアルゴリズムは、読み込まれたデータに対して現在のデータの解を与えることができます.
定数空間線形時間のオンラインアルゴリズムはほとんど完璧なアルゴリズムである.