arrays - ソートされていない配列で昇順の数字の最長シーケンスを見つける

Question

最大Array[10] = {10,6,11,9,-18,0,91,18,24,32} のシーケンスが10,11,18,24,32または-18,0,18,24,32

Array[10]これに対する解決策は、シーケンスの数を格納する別のものを作成することです。最後の要素 32 から始めて、1 つのシーケンス、つまり番号自体を作成します。

24 は 2を作る
18 は 3を作る
91 は 1を作る
0 は 4を作る
-18 は 5を作る
9 は 4を作る
11 は 4を作る
6 は 4を作る
10 は 5 を作る

出力は、-18 から始まる 5 または 10 から始まる 5 のいずれかになります。

誰でもコードを手伝ってくれませんか。

Answer 1

C++ で必要なもの。実行時間は O(NlogN) で、N は Array[] のサイズです。

#include<stdio.h>
#include<map>
using namespace std;

int main(void) {
        int Array[10] = {10,6,11,9,-18,0,91,18,24,32};
        int p[10],next[10];
        int i,j,n=10;
        map<int,int> places;
        for(i=n;i>=0;i--){
                map<int,int>::iterator ii=places.upper_bound(Array[i]);
                if(ii==places.end()){ //no item on the right is larger
                        p[i]=1;
                        next[i]=-1; 
                }else{
                        next[i]=ii->second;
                        p[i]=p[ii->second]+1;
                }
                places[Array[i]]=i;
                ii=places.find(Array[i]);
                while(ii!=places.begin()){
                        ii--;
                        if(p[ii->second]<=p[i]){
                                places.erase(ii);
                        }else
                                break;
                        ii=places.find(Array[i]);
                }
        }
        int longestI=0;
        for(i=1;i<n;i++){
                if(p[i]>p[longestI])
                        longestI=i;
        }
        for(i=longestI;i>=0;i=next[i]){
                printf("%d\n",Array[i]);
        }
        return 0;

}

Answer 2

多かれ少なかれそのように見えますが、これを使用している言語に翻訳する必要があります

largestSequience = [];
temporaryArray = [];
for (element in array)
{
if (temporatySize not empty and temporarySize[lastElement]>=element)
   {
    if (temporaryArray.length > largestSequence.length) largestSequence = temporaryArray;
    temporaryArray = [element]

   }

temporaryArray.add(element)

}