1

パール列 8 のプログラミングで見つかった問題は次のとおりです。

実数ベクトル x[n] を指定して、連続するサブベクトルで見つかった最大和を計算します。

提供される最終的なソリューションは、次のような O(n) の複雑さです。

std::vector<int> x;
int max_so_far = 0;
int max_here = 0;
for (std::size_t i = 0; i < x.size(); ++i)
{
   max_here = std::max(max_here + x[i], 0);
   max_so_far = std::max(max_so_far, max_here);
}

最小合計を提供するために上記のアルゴリズムを変更する方法を知りたいです。

4

1 に答える 1

2

各要素の符号を反転してからxアルゴリズムを実行するだけです。

std::vector<int> x;
int max_so_far = 0;
int max_here = 0;

for (std::size_t i = 0; i < x.size(); ++i) x[i] = -x[i];

for (std::size_t i = 0; i < x.size(); ++i)
{
   max_here = std::max(max_here + x[i], 0);
   max_so_far = std::max(max_so_far, max_here);
}

int min_so_far = -max_so_far;
于 2011-02-07T23:29:26.093 に答える