我们给出了一组数字，我们希望找到大小为4的子序列，按升序排序。
for eg ARRAY : -4 2 8 3 1 5
sorted subsequence of size 4 : -4 2 3 5
PS：有一种方法可以找到大小为3的排序子序列（see this）。我试图沿着相同的路线思考，但似乎无法找到4个整数的解决方案。
这是一个解决方案，通过对输入进行k+1传递，找到固定大小k的已排序子序列。每个传球都是从左到右完成的。
传递1：创建辅助阵列p1[0..n-1]。 p1[i]应该存储一个小于j的数字的索引arr[i]，并且位于arr[i]的左侧（换句话说：j<i和arr[j]<arr[i]）。如果没有这样的元素，p1[i]应该包含-1。 （p1与3号解决方案中的smaller数组相同）。
传递2：创建辅助阵列p2[0..n-1]。 p2[i]应该存储一个小于j的数字的索引arr[i]，位于arr[i]的左侧，并且p1[j] != -1（换句话说：j<i，arr[j]<arr[i]和p1[j]!=-1）。如果没有这样的元素，p2[i]应该包含-1。
....
传递k：创建一个辅助数组pk[0..n-1]。 pk[i]应该存储一个小于j的数字的索引arr[i]，位于arr[i]的左侧，并且p(k-1)[j] != -1（换句话说：j<i，arr[j]<arr[i]和p(k-1)[j]!=-1）。如果没有这样的元素，pk[i]应该包含-1。
在kth通过之后，pk[i] != -1对应于大小为k+1的排序子序列中的最大元素的每个元素。
kth pass的伪代码（k> 1）：
function do_kth_pass(pk[], p_k_minus_1[])
min = -1
for i in 0..n-1:
if min != -1 and arr[i] > arr[min]:
pk[i] = min
else
pk[i] = -1
if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]):
min = i
例：
Index: 0 1 2 3 4 5
Array: -4 2 8 3 1 5
p1: -1 0 0 0 0 0
p2: -1 -1 1 1 -1 4
p3: -1 -1 -1 -1 -1 3
3次传递后，你有p3 [5]！= -1，所以存在大小为4的已排序子序列。其元素的指数是：p1[p2[p3[5]]], p2[p3[5]], p3[5], 5，即0,1,3,5
拥有更大和更小的阵列是一个不错的选择，但它增加了空间复杂性。下面是一个解决方案，在线性子序列中找到四个数字而没有额外的数组空间，而是使用常量空间并且只在数组上传递一个。
#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_small部分，相同的代码也可用于数组中middle_2大小的排序子序列。
如果，相同的代码将扩展到k大小，然后在最小的i，我们必须记住i之前的所有最小值，即min_1，min_2，......直到min_i。只有在最后一个最小值，即我们子序列中的最大值，我们才会中断，并且不需要记住先前或当前的最小值。
如果发现任何错误，请告知！
你可以找到增长最长的子序列，看看它的大小是否大于等于4（如果你需要找到一个更一般的问题，甚至是k）。如果最长增加子序列的长度小于4（或k），则可以报告不存在此类子序列。 LIS可以在O(nlog(n))找到
创建一个smaller和greater数组，类似于为3的子序列所做的事情。除此之外，还有betweenSmallerAndCurrent数组，它存储最小值和当前元素之间的值的索引 - 包括值和在索引中。更明确地说：
betweenSmallerAndCurrent[i] = -1 or
input[smaller[i]] < input[betweenSmallerAndCurrent[i]] < input[value[i]] and
smaller[i] < betweenSmallerAndCurrent[i] < value[i]
构建它应该很容易。
你只需返回i指数，其中betweenSmallerAndCurrent[i]，smaller[betweenSmallerAndCurrent[i]]和greater[i]都已初始化。请注意，我们不能简单地检查smaller[i]，因为我们可能有类似[2,3,1,4,5]的东西，在这种情况下，当我们到达4时，第二个最小值3在当前最小值1之前。
例：
Indices: 0 1 2 3 4 5 6 7
Input: 12 11 10 5 6 2 9 30
smaller: -1 -1 -1 -1 3 -1 5 5
betweenSmallerAndCurrent:
-1 -1 -1 -1 -1 -1 4 4
greater: 7 7 7 7 7 7 7 -1
初始化所有值的唯一索引是6（输入值9）。
Java代码:(未经过广泛测试）
void find4Numbers(int arr[], int n)
{
int max = n-1; //Index of maximum element from right side
int min = 0, second = -1; //Index of minimum element from left side
int i;
// Create an array that will store index of a smaller
// element on left side. If there is no smaller element
// on left side, then smaller[i] will be -1.
int[] smaller = new int[n];
int[] betweenSmallerAndCurrent = new int[n];
smaller[0] = -1; // first entry will always be -1
betweenSmallerAndCurrent[0] = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[min])
{
min = i;
smaller[i] = -1;
betweenSmallerAndCurrent[i] = -1;
}
else
{
smaller[i] = min;
if (second != -1 && arr[second] < arr[i])
betweenSmallerAndCurrent[i] = second;
else
betweenSmallerAndCurrent[i] = -1;
if (second == -1 || arr[i] < arr[second])
second = i;
}
}
// Create another array that will store index of a
// greater element on right side. If there is no greater
// element on right side, then greater[i] will be -1.
int[] greater = new int[n];
greater[n-1] = -1; // last entry will always be -1
for (i = n-2; i >= 0; i--)
{
if (arr[i] >= arr[max])
{
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Make sure they're right
System.out.println(Arrays.toString(smaller));
System.out.println(Arrays.toString(betweenSmallerAndCurrent));
System.out.println(Arrays.toString(greater));
// Now find a number which has both a greater number on
// right side and smaller number on left side
for (i = 0; i < n; i++)
{
if (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1)
{
System.out.printf("%d %d %d %d\n",
arr[smaller[betweenSmallerAndCurrent[i]]],
arr[betweenSmallerAndCurrent[i]],
arr[i],
arr[greater[i]]);
return;
}
}
// If we reach number, then there are no such 3 numbers
System.out.println("No such triplet found");
}
您可能会注意到主要代码从this更改，除了C到Java转换和添加的初始化之外，还在于设置smaller的循环。代码应该很容易理解 - 如果遇到问题，请尝试将其翻译成单词。
Test。
对于每个元素，找到下一个更大的元素索引else -1现在将其视为图形并找到长度为k的路径（如果存在）这可以使用哈希表和memoization在线性时间内轻松完成。