相关疑难解决方法(0)

给定一个包含N个不同整数的数组,找到满足以下条件的最长子序列:

1. 子序列的start元素是子序列中最小的.
2. 子序列的结束元素是子序列中最大的元素.

例如:8,1,9,4,7.答案是1,4,7.

2,6,5,4,9,8.答案是2,6,5,4,9或2,6,5,4,8.

这是一个O(N^2)算法:

• 让我们X成为一组数字.
• 迭代X.假设我们在索引i.让Y是阵列,其中Y [j]为在元件的数量(j, i],其比X [j]的小.让z是元件的数量在[j, i]其比X [I]小.如果X [j]小于X [i],我们可以得到满足约束的长度为zY [j]的子序列.

• 设置z为1.循环j从i-1下到0.

  if X[j] < X[i]: z++; ans = max(ans, z - Y[j]); else Y[j]++;

我们可以做得更好吗？我认为应该有一个O(NlogN)算法来找到最大长度.