arrays - 線形時間で配列内のサイズ 4 の並べ替えられたサブシーケンスを見つける

Question

数値の配列が与えられ、昇順でソートされたサイズ 4 のサブシーケンスを見つけたいとします。

for eg ARRAY                :  -4 2 8 3 1 5
sorted subsequence of size 4 : -4 2 3 5

PS: サイズ 3 のソートされたサブシーケンスを見つける方法があります (これを参照)。私は同じように考えようとしていますが、4 つの整数の解決策を見つけることができないようです。

Answer 1

より大きな配列とより小さな配列を持つことは良いオプションですが、スペースの複雑さが増します。以下は、追加の配列スペースを使用せずに線形サブシーケンスで 4 つの数値を検索するソリューションですが、一定のスペースを使用し、配列を 1 回だけパスします。

#include <iostream>

void sortedSubseqFour(int a[], int n)
{
    int small = INT_MAX;
    int middle_1 = INT_MAX;
    int middle_2 = INT_MAX; 
    int greater = 0;

    int main_small = 0;
    int main_middle_1 = 0;

    int main_main_small = 0;

    for(int i = 0; i<n; i++)
    {
        if (a[i] <= small)
            small = a[i];
        else if (a[i] <= middle_1)
        {
            middle_1 = a[i];
            main_small = small;
        }
        else if (a[i] <= middle_2)
        {
            middle_2 = a[i];
            main_middle_1 = middle_1;
            main_main_small = main_small;
        }
        else
        {
            greater = a[i];
            break;
        }
    }
    //end of loop

    if (greater != 0)
        std::cout << main_main_small << '\t' << main_middle_1 << '\t'
                  << middle_2 << '\t' << greater;
    else
        std::cout << "No such Quadruple";
}

int main()
{
    int arr[10] = {6, 7, 5, 1, 4, 3, 0, 7, 2, 11};
    int n = 10; 

    sortedSubseqFour(arr, n);
    return 0;
}

上記のアプローチは、現在の最小値を設定するときに、最小値のすべてのレイヤーを記憶します。コードの一部を3削除することにより、同じコードを配列内のサイズの並べ替えられたサブシーケンスに使用することもできます。main_main_smallmiddle_2

同じコードを最小サイズまで拡張する場合、すべてkの最小i値を記憶する必要があります。最後の最小値、つまりサブシーケンスの最大値でのみブレークし、以前または現在の最小値を覚えておく必要はありません。imin_1min_2min_i

バグが発見された場合はお知らせください。