問題タブ [subsequence]

例：

-4 -10 -15 - 20 100 -67 47 20配列は次の とおりです。k = 51

期待される出力:

-4 -10 -15 - 20 100

-4 -10 -15 - 20 100 -67 47 20

O（n ^ 2）でブルートフォースソリューションを試しました。誰でもこれに対するより良い解決策を提案できますか?

多くの異なる UniqueID を持つデータフレームがあり、これも日付順に並べられています。各 UniqueID は、古い日付から新しい日付の順に並べ替えられます。また、1 から 4 までの順序で並べられた、steps という列もあります。

各 UniqueID の目標は、最初のステップの最も古いインスタンス、次に 2 番目のステップの最も古いインスタンスなどを見つけることです。いくつかのステップが欠落している可能性があります。たとえば、ステップ 3 が UniqueID = "B" の場合に欠落しています。この場合、ステップ 3 をスキップしてステップ 4 に進みます。

これが元のデータフレームです。

選択する有効なエントリは、観測 3、6、8、12、14、17 です。このデータフレームを作成します。

ロジックといくつかの疑似コードがありますが、まとめることはできません。したがって、UniqueID = "A" のデータ フレームの例では、最初にデータ フレームをグループ化します。

group_by(UniqueID)

UniqueID = "A" の最小値を見つけて、変数に割り当てます。

v <- min(Step)1 を返します

次に、このステップのインデックスを取得します

i <- which.min(Step)3 を返します

次に、最初のステップよりも大きい最小ステップを見つけ、最初のステップの後に発生する要素のみを検索します。そのため、1 を超える Step の値のみを検索し、最初に見つかった値の位置から、この場合は観察 3 からのみ検索します。次のいずれかになるまで、各 UniqueID のすべての観察に対してこれを繰り返し続けたいと考えています。最後の観測に到達するか、残りの要素で最後の観測よりも大きい観測を見つけることができなくなります。

サンプルデータフレームを作成するための出力は次のとおりです。

jeremycg のメソッドを使用してクラッシュする代替 dput。

編集: jeremycg から更新されたコードを使用してもクラッシュし続ける UniqueID の出力:

私は動的プログラミングが初めてで、最長増加部分列 (LIS) 問題を読んでいました。

ソリューションは、シーケンスが元の配列のように連続している必要はないと述べました。要素は途中でスキップできます。しかし、私は別の印象を受けました。

この混乱を明確にするのを手伝ってください。

例を挙げてみましょう: a = {10,22,9,33,55,66,12,90} LIS は{10,22,33,55,66,90} => 6

しかし、私はそうなると思った{33,55,66}

ありがとう

正の整数の配列が与えられた場合、配列内の減少していないサブシーケンスの数を調べたいと思います。

たとえば、配列が の場合{6,7,8,4,5,6}、非減少サブシーケンスは{6},{7},{8},{4},{5},{6},{6,7},{7,8},{4,5},{5,6},{6,7,8},{4,5,6}12 のようなシーケンスになります

m 個の整数のn 個のソートされた配列を固定順序で持っています。サブシーケンスのすべての要素が正確に 1 つの配列に属するように、最も長く増加するサブシーケンスを見つける必要があります。O (n ² )よりもうまくできるでしょうか?

1 つの arrayA が arrayB のサブシーケンスであるかどうかをチェックする、再帰的プログラミングと動的プログラミングの両方のさまざまなアルゴリズムを調査しようとしています。例えば、

私はいくつかの異なる検索を試みましたが、見つけることができるのは、最長増加部分列を計算するアルゴリズムだけです。

数値の配列が与えられ、質問は、長さがlis-1の増加するサブシーケンスの総数を見つけることです。ここで、lisはその特定の配列の長さです。 Largest Increasing sub-sequence

例:配列が であるとし5 6 3 4 7 8ます。ここで、lis = 4です。したがって、lis-1 = 3です。したがって、サブシーケンスの総数は次の8とおりです。

誰かがこのアルゴリズムのアイデアを教えてくれますか?私はそれを理解することができません.

指定された配列内の最長のサブシーケンスの合計と長さをカウントしたかったのtです。

出力される数値について1 1 7 3 2 0 0 4 5 5 6 2 1：

sum is 20 length is 6

しかし、同じ番号を逆の順序1 2 6 5 5 4 0 0 2 3 7 1 1で出力すると、次のようになります。

sum is 17 length is 6を取得する必要があるため、これは正しくありませsum is 12 length is 5ん。

誰かが私の間違いを見つけることができますか?