在 kdb 中找到最大 j – i 使得 arr[j] > arr[i] （距离最大化问题）

Question

找到最大 j – i 使得 arr[j] > arr[i] （距离最大化问题） 输出：6（j = 7，i = 1）

q)list: 34 8 10 3 2 80 30 33 1

q)func:{{first[y _ x],/: (y+1) _ x}[x] each y}

q)func[list;til count list]
(34 8;34 10;34 3;34 2;34 80;34 30;34 33;34 1)
(8 10;8 3;8 2;8 80;8 30;8 33;8 1)
(10 3;10 2;10 80;10 30;10 33;10 1)
(3 2;3 80;3 30;3 33;3 1)
(2 80;2 30;2 33;2 1)
(80 30;80 33;80 1)
(30 33;30 1)
,33 1
()

q)asc r where {(x 1)>(x 0)} each r:raze  func[list;til count list]
2  30
2  33
2  80
3  30
3  33
3  80
8  10
8  30
8  33
8  80
10 30
10 33
10 80
30 33
34 80

我在这里找到最终结果，请对此提出建议。

Answer 1

这不是最佳/优化的，但在思考问题时表格可能是有用的结构。

从列表中创建一个表，并将索引存储为

ind

以及数组值

arr

:

q)t:{`arr xdesc ([] arr:x;ind:til count x)}[list]
q)t
arr ind
-------
80  5
34  0
33  7
30  6
10  2
8   1
3   3
2   4
1   8

计算索引偏移量

off

到每个值

>

当前

arr

值并存储它们的

ind

:

q)t:update calc:{[x;y]select ind,off:y-ind from t where x>arr,y>ind}'[arr;ind] from t
q)t
arr ind calc
---------------------------------------
80  5   +`ind`off!(0 2 1 3 4;5 3 4 2 1)
34  0   +`ind`off!(`long$();`long$())
33  7   +`ind`off!(6 2 1 3 4;1 5 6 4 3)
30  6   +`ind`off!(2 1 3 4;4 5 3 2)
10  2   +`ind`off!(,1;,1)
8   1   +`ind`off!(`long$();`long$())
3   3   +`ind`off!(`long$();`long$())
2   4   +`ind`off!(`long$();`long$())
1   8   +`ind`off!(`long$();`long$())

ungroup

用于最终过滤：

q)t:ungroup t
q)t
arr ind calc
--------------------
80  5   `ind`off!0 5
80  5   `ind`off!2 3
80  5   `ind`off!1 4
80  5   `ind`off!3 2
80  5   `ind`off!4 1
33  7   `ind`off!6 1
33  7   `ind`off!2 5
33  7   `ind`off!1 6
33  7   `ind`off!3 4
33  7   `ind`off!4 3
30  6   `ind`off!2 4
30  6   `ind`off!1 5
30  6   `ind`off!3 3
30  6   `ind`off!4 2
10  2   `ind`off!1 1

提取偏移量最大的行：

q)select from t where calc[;`off] = max calc[;`off]
arr ind calc
--------------------
33  7   `ind`off!1 6

输出：计算出的偏移量

calc[;`off]

最大值为

6

，从索引

ind

7

到

calc[;`ind]

1