n 個の数字のリストが与えられますL=<a_1, a_2,...a_n>。それぞれは 0 か、+/- 2 k , 0 <= k <= 30 の形式です。 CONTINUOUS SUBLIST の最大積を返すアルゴリズムを説明、実装してください
p=a_i*a_i+1*...*a_j, 1 <= i <= j <= n。
たとえば、入力の<8 0 -4 -2 0 1>場合は 8 (8 または (-4)*(-2)) を返す必要があります。
任意の標準プログラミング言語を使用でき、リストが任意の標準データ構造 ( 、int[]、
など) で与えられていると想定できます。vector<int>List<Integer>
アルゴリズムの計算の複雑さは?
私の最初の答えでは、「2つの大きな大きな数を掛ける」というOPの問題に対処しました。結局のところ、この願いは、これから取り組もうとしているより大きな問題のほんの一部にすぎません。
「アルゴリズムの最終的な骨組みにまだ到達していません。これを手伝ってもらえないでしょうか。」
(問題の説明については、質問を参照してください)
私がやろうとしているのは、アムノンが提案したアプローチをもう少し詳しく説明することだけです。
2 の累乗である整数のリストから連続サブリストの最大の積を見つける必要があります。アイデアは次のとおりです。
startサブリストは、endインデックスで表すことができます。にはstart=0n-1 の可能な値end、つまり 0..n-1 があります。これにより、インデックス 0 で始まるすべてのサブリストが生成されます。次の反復では、start1 ずつインクリメントしてプロセスを繰り返します (今回は、 の可能な値は n-2 ですend)。このようにして、可能なすべてのサブリストを生成します。
さて、これらのサブリストのそれぞれについて、その要素の積を計算する必要があります - それはメソッドを考え出すことcomputeProduct(List wholeList, int startIndex, int endIndex)です. 組み込みBigIntegerクラス (割り当てによって提供される入力を処理できるはずです) を使用して、さらなるトラブルからあなたを救うか、他の人が説明したように、より効率的な乗算方法を実装しようとすることができます。(アルゴリズムが正しく機能するかどうかを確認し、最初に最適化を試みる方が簡単なので、より単純なアプローチから始めます。)
すべてのサブリストを繰り返し処理し、それらの要素の積を計算できるようになったので、最大の積を持つサブリストを決定するのが最も簡単な部分になるはずです。
それでも 2 つのステップを結び付けるのが難しい場合はお知らせください。ただし、問題に取り組んでいるときは、コードのドラフトも提供してください。それをコピー＆ペーストします。
public BigInteger listingSublist(BigInteger[] biArray)
{
int start = 0;
int end = biArray.length-1;
BigInteger maximum;
for (int i = start; i <= end; i++)
{
for (int j = i; j <= end; j++)
{
//insert logic to determine the maximum product.
computeProduct(biArray, i, j);
}
}
return maximum;
}
public BigInteger computeProduct(BigInteger[] wholeList, int startIndex,
int endIndex)
{
//insert logic here to return
//wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
// wholeList[endIndex]);
}
実際、乗算の最も効率的な方法は、代わりに足し算を行うことです。この特別なケースでは、2 のべき乗の数だけがあり、指数を足すだけでサブリストの積を得ることができます (積の負の数を数え、奇数の場合は負の数にします)。ネガ）。
もちろん、ビットが足りなくなった場合は、結果を格納するために BigInteger が必要になる場合があります。または、出力がどのように見えるかによって、(+/-)2^N とだけ言います。ここで、N は指数の合計です。
処理する数字は 30 個しかないため、入力の解析は大文字と小文字の切り替えの問題になる可能性があります。プラスマイナス。
それは退屈な部分です。興味深い部分は、最大数を生成するサブリストを取得する方法です。すべてのバリエーションをチェックすることで、愚かなアプローチをとることができますが、それは最悪の場合 (IIRC) に O(N^2) アルゴリズムになります。これは、長い入力にはあまり適していません。
あなたは何ができますか？おそらく、リスト内の最大の負でない数からサブリストとして開始し、サブリストを成長させて、各方向にできるだけ多くの負でない数を取得します。次に、すべてのポジティブに到達したら、両側のネガティブのペアに進みます。リストの両側で成長できる場合にのみ成長します。両方の方向に成長できない場合は、2 つ (4 つ、6 つなど) の連続した負の数で 1 つの方向を試してください。この方法でも成長できない場合は、停止してください。
このアルゴリズムが機能するかどうかはわかりませんが、機能する場合 (または同様のもの) は O(N) アルゴリズムであり、優れたパフォーマンスを意味します。試してみましょう！:-)
k <= 30 なので、任意の整数 i = 2 kは Java に収まりますint。intただし、 Java に2 k * 2 k = 2 2*k <= 2 60を満たすため、このような 2 つの整数の積は必ずしも Java に適合するとは限りませんlong。これは、「2つの数字の（乗算）...」に関するあなたの質問に答えるはずです。
2つ以上の数値を乗算したい場合は、「... CONTINUOUS SUBLISTの最大積...」（サブリストの長さが> 2になる可能性があります）という割り当てによって暗示されますが、JavaのBigIntegerクラスを見てください。 .
うーん..それらはすべて2の累乗であるため、数値を掛ける代わりに指数を追加するだけで済みます(製品の対数を取ることに相当します)。たとえば、2^3 * 2^7 は 2^(7+3)=2^10 です。記号の扱いは、読者の演習として残しておきます。
サブリストの問題に関しては、(begin,end) インデックスのペアが n^2 未満です。それらをすべてチェックするか、動的計画法ソリューションを試すことができます。
編集:実際の疑似コードと一致するようにアルゴリズムの概要を調整し、複雑さの分析を答えに直接入れました:
アルゴリズムの概要
シーケンスを順番に調べ、最後の 0 以降の積 (正) の値と最初/最後のインデックスを格納します。シーケンスの最初の符号変更以降の数値のみで構成される別の積 (負) についても同じことを行います。負のシーケンス要素にヒットした場合は、関連付けられた開始インデックスと共に 2 つの積 (正と負) を交換します。正の積が新しい最大値に達するたびに、それと関連する開始インデックスと終了インデックスが保存されます。シーケンス全体を調べた後、結果は最大変数に格納されます。
オーバーフローを避けるために、バイナリ対数と追加の符号で計算します。
疑似コード
maxProduct = 0
maxProductStartIndex = -1
maxProductEndIndex = -1
sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0
for every index of sequence
n = sequence[index]
if n == 0
posProduct = 0
negProduct = 0
posProductStartIndex = index+1
negProductStartIndex = -1
else
if n < 0
swap( posProduct, negProduct )
swap( posProductStartIndex, negProductStartIndex )
if -1 == posProductStartIndex // start second sequence on sign change
posProductStartIndex = index
end if
n = -n;
end if
logN = log2(n) // as indicated all arithmetic is done on the logarithms
posProduct += logN
if -1 < negProductStartIndex // start the second product as soon as the sign changes first
negProduct += logN
end if
if maxProduct < posProduct // update current best solution
maxProduct = posProduct
maxProductStartIndex = posProductStartIndex
maxProductEndIndex = index
end if
end if
end for
// output solution
print "The maximum product is " 2^maxProduct "."
print "It is reached by multiplying the numbers from sequence index "
print maxProductStartIndex " to sequence index " maxProductEndIndex
複雑
このアルゴリズムは、シーケンス全体で単一のループを使用するため、ループ本体の複雑さは O(n) 倍になります。ボディの最も複雑な操作は log2 です。したがって、log2 の O(n) 倍の複雑さになります。制限されたサイズの数の log2 は O(1) であるため、結果の複雑さは O(n) 別名線形です。
2 の累乗の乗算に関する Amnon の観察と、サブリストに関する私の観察を組み合わせたいと思います。
リストは 0 で完全に終了します。問題を分割して、各サブリストで最大の製品を見つけ、次にその最大値を見つけることができます。（他の人がこれについて言及しています）。
これは、この記事の 3 回目の改訂です。でも3が魅力…
アプローチ
0 以外の数字のリストが与えられた場合 (これには多くの検討が必要でした)、3 つのサブケースがあります。
リストには奇数の負の数が含まれているため、すべての数の積は負になります。符号を変更するには、負の数を含むサブシーケンスを犠牲にする必要があります。2 つのサブケース:
a. 左から左端の負の数までの数を犠牲にします。また
b. 右から右端のマイナスまでの数字を犠牲にします。
どちらの場合も、残りの数の積を返します。ちょうど 1 つの負の数を犠牲にすると、結果は確実に正になります。(a) と (b) の勝者を選びます。
実装
入力は、0 で区切られたサブシーケンスに分割する必要があります。リストをループして、0 以外のシーケンスの開始と終了を選択するようにドライバ メソッドが構築されている場合、リストはその場で処理できます。
long で計算を行うと、可能な範囲が 2 倍になるだけです。log2 に変換すると、大きな積の計算が簡単になります。多数の大きなシーケンスでプログラムが失敗するのを防ぎます。別の方法として、すべての計算を Bignum で行うこともできますが、おそらくパフォーマンスが低下します。
最後に、まだ log2 の数値である最終結果を、印刷可能な形式に変換する必要があります。そこで Bignum が役に立ちます。new BigInteger("2").pow(log);2 を 乗するものがあり ますlog。
複雑
このアルゴリズムは、サブリストを順番に処理し、各サブリストを 1 回だけ処理します。各サブリスト内では、入力を log2 に変換して結果を戻すという面倒な作業がありますが、この作業はリストのサイズに比例します。最悪の場合、リストの大部分の合計が 2 回計算されますが、これも線形の複雑さです。
このコードを参照してください。ここでは、非常に大きな数の正確な階乗を実装します。大きな数字を作るために整数配列を使用しているだけです。Planet Source Codeからコードをダウンロードします。