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]将存储序列数的。从仅构成 1 个序列的最后一个元素 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

你在 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)

}