問題タブ [kadanes-algorithm]

サブアレイの最大積の範囲を取得しようとしています (就職の面接のために勉強しています)。

これはすでにここで質問されています (ただし、有効な回答は提供されていません)。 Kadanes アルゴリズムを使用して最大積部分配列の範囲を取得する

トリック/アルゴリズムはここでよく説明されています: http://www.geeksforgeeks.org/maximum-product-subarray/

最大積を簡単に取得できますが、何度も試行しても、範囲を取得する方法がわかりません (左右のインデックスが適切に)。誰でも助けてもらえますか??

コードを貼り付けたので、コピーしてすぐに実行できます..

出力例は次のとおりです。

ご覧のとおり、最大積を取得していますが、範囲が間違っています。

助けてください。

数値の配列が与えられた場合、最小合計を見つけます。部分配列の長さは 0 にはなりません。

kadane のアルゴリズムを使用できることはわかっていますが、サブ配列の長さが 0 であってはならないという質問が必要です。したがって、私の実装では、配列のすべての要素が正の場合を処理できません。

たとえば、配列が 2、5、3、8、4 の場合、最小合計は 2 です。

-5、-4、5、-1、2、最小合計は -9 (最初の 2 つの要素の合計) のような通常の配列でも動作する必要があります。

どうすればこれを達成できますか?

これが私の実装です：

A(正と負の) 整数を含む配列があります。要素の絶対合計が最小である (連続した) サブ配列を見つけます。

正しい結果が得られましたがO(N^2)、 orであったブルートフォースアルゴリズムを実装することから始めました。O(N^3)ただし、タスクは次のように指定します。

いくつか検索した後、この問題に合わせて Kadane のアルゴリズムを変更できるのではないかと考えましたが、失敗しました。

私の質問は - Kadane のアルゴリズムは正しい方法ですか? そうでない場合は、正しい方向に向けていただけますか (または、ここで役立つアルゴリズムを挙げてください)。既製のコードは必要ありません。適切なアルゴリズムを見つけるための助けが必要なだけです。

私は Prolog を初めて使用し、部分配列の最大問題のインスタンスを解決しようとしています。

次の非常にエレガントな C++ コードを取得しました。

そして、ここに私のプロローグコードがあります:

から最大合計を取得しようとしますf(L,M,N)。LはリストでMあり、結果です (最大合計は、C++ コードの変数「maxsofar」と同様です)。取得したいのNは、C++ コードの「maxendinghere」としての中間変数です。L以前のリストからの答えを得たいのですL1が、変数の関係は C++ コードとまったく同じです。

ただし、次のクエリは機能しません。

どこに問題があるのか​​わからない。

Cormen の「Introduction to Algorithms」を読んでいます。

Max Sum Subarray 問題の線形アルゴリズムについては、独自の解決策を考え出しました。実装前に既存のもの（カデナのもの）をチェックしていませんでした。

現在、さまざまなテスト シナリオでテストしており、常に Kadena のものよりも優れた結果が得られています。私はそのような幸運を信じていませんが、私が逃したものを見つけることはできません. それが実用的な解決策であるかどうかを見ていただけますか？

更新 コードの考え方は、1 つのサブ配列のみを追跡し、その末尾の数値に追加することです。数値が非常に低い場合、合計が負になるため、末尾の後に配列の先頭を設定します。さらに、冒頭の否定的な項目は無視されています。サブ配列の先頭が前方にシフトされます。合計が最大に見えるたびに - maxSum と制限が更新されます。

+ve と -ve integer を持つ配列を指定して、連続する 2 つの要素をスキップできないような最大合計を見つけます (つまり、先に進むにはそれらの少なくとも 1 つを選択する必要があります)。

例:-

10、20、30、-10、-50、40、-50、-1、-3

出力 : 10+20+30-10+40-1 = 89

質問は：

2D 配列 [1:m,1:n] が与えられた場合、1<=a<=b<=m および 1<=c<=d である部分配列の最大和 [a:b,c:d] を見つける必要があります。 <=n で、配列の要素の合計が (Summation)A[i,j] となるように、時間計算量 O(mn min(m,n ) log max(m,n))

問題の解決方法を知りたいのですが、次のように考えていました-

1) 各行で Kadane のアルゴリズムを使用して、2x2 行列の中央から左右に向かって各要素の累積和を求めます。

2) 昇順に基づいて右側の合計を並べ替えます

3)左側の各要素を右側の最大要素にマップし、最大値を持つ行を選択します。

4)2×2の行列の真ん中から上下に向かって同じ手順を繰り返す(累積和)

5) 手順 2 と 3 を繰り返します。

6) 両方の方法で得られた最大値を結合し、それを最大合計部分配列として使用します

これは、特定の配列からサブ配列（連続）の最大合計を見つけるための私のプログラムです。kadane のアルゴリズムを使用すると非常に簡単です。

しかし、最大合計を持つ連続したサブ配列の開始位置と終了位置も見つけたいです。それを行うために上記のプログラムに数行追加しようとしましたが、うまくいきませんでした。私の質問は、最大合計を持つそのサブ配列の開始位置と終了位置を取得するにはどうすればよいですか? ありがとう。

私たちのほとんどは、部分配列の最大和問題に精通しています。私はこの問題の変種に遭遇しました。これは、ある数 M を法とするすべての部分配列の和の最大値を出力するようにプログラマーに要求するものです。

このバリアントを解決するための素朴なアプローチは、可能なすべての部分配列の合計を見つけることです (N は配列のサイズである N^2 のオーダーになります)。もちろん、これでは十分ではありません。問題は、どうすれば改善できるかということです。

例: 次の配列を考えてみましょう。

6 6 11 15 12 1

M = 13 とします。この場合、サブアレイ 6 6 (または 12 または 6 6 11 15 または 11 15 12) は最大合計 ( = 12 ) を生成します。