algorithm - 有约束的数字序列

Question

我有一个正数序列 x_1,x_2,...x_n，我想找到一个连续的子序列，其中:0< x_i-x_j < i-j , 1<= j< i <= n 对所有 i 都成立， j.定义S(t)为以x_t结尾的最长连续序列的长度..

例如如果S(t) = 3 那么以上对 x_t,x_{t-1},x_{t-2}

成立

我试图找到一个递归公式，但我完全被卡住了。为了找到一些模式，我试着玩弄数字:

S(5) = 2 意味着 S(5) = 2 + S(4) 并且 S(4) 必须为 $0$。但是 S(3) 可能为 1，因此我们必须尽快停止我们发现 S(4) = 0

基本情况或特殊情况 S(0) = 0 ,S(1) = 0？

是否可以将 S(k) 写成 S(k-1)？

我正在尝试为此构建一个算法，但首先我需要找出一个递归公式。

Answer 1

S(0) = 0
如果 (x_n <= x_{n-1} 或 x_n - x_{n-1} >= 1) => S(n) = 0
否则如果 S(n-1) = 0 => S(n)=2
否则 S(n) = S(n-1) + 1