查找升序編號的最長序列中排序的數組

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開始，它只產生一個序列，即數字本身。

24使2
18使3
91使1
0使得4
-18使得5
9使4
11使得4
6使4
10使5

輸出應該是從-18開始的5或從10開始的5輸出。

任何人都可以幫助我的代碼請。

Answer 1

或多或少它看起來就像是，現在你需要把這個翻譯成語言使用的是

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) 

} 

Answer 2

要在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; 

}