問題タブ [subsequence]

整数要素のシーケンスSが与えられた場合、次のようなインデックス i とインデックス j (両方を含む) の間のシーケンスの最小要素を見つける関数が必要です。nmin(i,j)

1. 初期化には時間がかかりO(n)ます。
2. メモリ空間O(n);
3. min(i,j)かかりますO(log(n))。

このためのアルゴリズムを提案してください。

JSONファイルを解析しようとしています。やや構造から外れていたので、構造を取得するために、そのファイルのサブシーケンスを使用しています（構造を取得するため）。しかし、サブシーケンスまたはサブストリングを使用しているときは、開始オフセット (最初のオフセット) を省略しているだけであり、終了オフセット (終了はそのまま) を省略しています。コードは次のとおりです。

また、文字数を数えて終了オフセットを設定しようとしましたが、それでも指定した文字数を超えています。

サブシーケンスを扱うコーディング チャレンジ サイトからの質問に出会いました。

整数要素の配列が与えられると、この配列のサブシーケンスは、配列からの連続した要素のセットになります (つまり、配列 v: [7, 8, -3, 5, -1] が与えられると、v のサブシーケンスは 8、 -3, 5)

あなたの仕事は、次の条件を満たす配列の左と右のサブシーケンスを見つける関数を書くことです:

1. 2 つのサブシーケンスは一意である必要があります (共有要素はありません)。

2. 右側の部分列の要素の合計と左側の部分列の要素の合計の差は最大です

3. 差分を標準出力 (stdout) に出力します。

この関数は、整数の配列である array を受け取ります。

データの制約:

1. 配列には、少なくとも 2 つ、最大で 1,000,000 の数字があります

2. 配列内のすべての要素は、次の範囲の整数です: [-1000, 1000]

例

上記の例では、左側のサブシーケンスは [-5, 1, -2] であり、右側のサブシーケンスは [8,-2,3] です。

これが私が試したことです

しかし、それはうまくいかないようです。

最大部分列合計プログラムの再帰的解法に基づいた最大部分列積プログラムを作成しようとしています (つまり、同じ形式に従います)。

これまでのところ、結果が「0」になる場合を除いてすべてのケースで機能し、シーケンス内に正の製品がないことを示します。以下の 5 つのシーケンスでは、最後のシーケンスを除くすべてのシーケンスで機能します。

a はシーケンス、p1 は最初は a[0]、p2 は a[最後のインデックス] です。

'checkForSplit' に関する注意。a[i] == 0 でない限り、値は 0 です。現在のサブシーケンスの左端または右端のインデックスをチェックしています。この場合、1 に設定されます。これにより、' の別の計算がトリガーされます。 max3' ここで、PL は PR で乗算されません。ロジックは、PL または PR のいずれかが 0 の場合、2 つのうちの他方がそうでない可能性があり、その場合、それらを乗算するべきではないということです。

前述したように、このアルゴリズムは 5 番目のシーケンスを除くすべてのシーケンスで機能します。

何か案は？

サブアレイ、サブシーケンス、サブセットの間で少し混乱しています

私が持っている場合{1,2,3,4}

それから

subsequence は{1,2,4}OR{2,4}などにすることができます。したがって、基本的にはいくつかの要素を省略できますが、順序は維持できます。

サブアレイは次のようになります（サイズ3のサブアレイと言います）

それでは、サブセットは何でしょうか？

この3つで少し迷っています。

2 つの文字列が与えられた場合、与えられた文字列が文字列のサブシーケンスになるように、長さが最小の文字列を見つける必要があります。つまり、一部の文字を削除すると指定された文字列になるような文字列を見つける必要があります。ブルートフォースとLCSを考えていましたが無駄でした。

12345 と 11234 は 112345 WWA になり、WWS には応答 WWAS があります

LCS はかなりメモリ効率が悪く (DP のもの)、総当りは幼稚です。私は何をすべきか？

シーケンスの変位を最大要素と最小要素の差と定義します。与えられた整数のシーケンスについて、長さ の連続するすべてのサブシーケンスの最大変位を見つけますm。

たとえば、シーケンスが [1, 5, 7, 0, 2, -4] で m = 3 の場合、

• [1, 5, 7] の変位は 6 です。
• [5, 7, 0] の変位は 7 です。
• [7, 0, 2] の変位は 7 です。
• [0, 2, -4] の変位は 6 です。
• したがって、最大変位は 7 です。

入力シーケンスの長さを n とすると、以下の私のソリューションは O(nlog(m)) 時間で実行されます。より良い方法はありますか？私が見逃している線形時間アルゴリズムがあるに違いないと感じています。この質問の目的のために、私が気にするのは漸近的な時間の複雑さだけです。

二次最大連続サブシーケンス合計アルゴリズム

アルゴリズムがどのように機能するかを誰かが説明できるかどうか疑問に思っていましたか? for ループは得意ですが、入れ子になったループは苦手です。「thisSum」は、8 行目の外側の for ループが実行されるたびに常に 0 ですか、それとも静的ですか?

どうもありがとうございました！私はアルゴリズムを理解するために一生懸命努力しています。私を助けてください！時間と労力を本当に感謝しています。