arrays - 配列内の非減少サブシーケンスの数を見つけるにはどうすればよいですか?

Question

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

たとえば、配列が の場合{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 のようなシーケンスになります

Answer 1

最長増加サブシーケンスのよく知られた二次解法と同様の動的計画法のアプローチを使用できます。

a[i]入力配列にしましょう。c[i]で終わる非減少サブシーケンスの数を としますa[i]。そのようなサブシーケンスでc[i]先行する数を調べることで、簡単に計算できます。それよりも前(つまり)で、それより大きくない ( )a[i]任意の数値を指定できます。1 要素のサブシーケンスも忘れないでください。これにより、次の疑似コードが生成されます。a[j]a[i]j<ia[j]<=a[i]{a[i]}

c[0] = 1
for i = 1..n-1
    c[i] = 1 // the one-element subsequence
    for j = 0..i-1 
        if a[j]<=a[i]
            c[i] += c[j]

---

最長増加サブシーケンスの数も参照してください。最長のシーケンスのみを検索しますが、そのようなシーケンスもすべてカウントするように変更できると思います。