有約束的序列號

我有正數X_1，X_2，... x_n的順序，我想找到一個連續的序列，其中：0 < X_I-x_j < IJ，1 < = j的<我< = N所有我，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（0）= 0，S（1）= 0時，我們必須立即停止S（4）= 0

基礎案例或可能特殊情況。

是否可以用S（k-1）來寫S（k）？

我想構建一個算法，但首先我需要找出一個遞歸公式。

2017-02-14 J.doe

你能給你的意思的例子由「連續子序列」和「數字」？從名字來看，它聽起來應該是連續的整數 - 例如，0,2,3,4,5,4的最大連續子序列應該是2,3,4,5。但是這並不能滿足你提供的定義。 –

在您的重複中，1的序列似乎無效。這是錯誤還是有意？它絕對與通常的序列定義相矛盾。 – Paul

S（0）= 0
如果（x_n < = X_ {N-1}或x_n - X_ {N-1}> = 1）=> S（N）= 0
否則，如果S（（n-1）+ 1

2017-02-14 14:33:34 AnotherGeek

不知道結果會是1而不是0在問題'基本情況或可能特殊情況S（0）= 0，S（1）= 0'，所以它似乎函數將有0,2,3 ...作爲結果，但從來沒有1 – AnotherGeek

沒有注意到，調整。我想這需要OP的一些澄清。 – Paul

在這個問題中不需要動態編程或遞歸由於簡單比較運算符的關係：它是可傳遞的。這意味着：

a < b and b < c => a < c

我們可以將上述不等式一點：

x_i - x_j < i - j 
x_i - i < x_j - j

這使得整個問題變得簡單許多：
定義序列y，其中y_i = x_i - i。找到結尾爲y_t的最長嚴格遞減序列。

由於嚴格遞減序列中的傳遞性，您的條件總是成立，反之亦然。實際上，這兩個約束在這種情況下是等價的，因爲不能有一個既不減少又不違反序列約束的約束。所以在這種情況下根本不需要遞歸，因爲線性關係是完全足夠的（傳遞性）。

你當然會這樣搜索的第一個非遞減對轉化爲一個遞歸函數（儘管它更復雜得多，只是去線性路徑）：

S(t) = {t = 0:        0 
     t = 1:        1 
     {x_t - t >= x_{t-1} - (t - 1)}: 1 
     else:        1 + S(t - 1)}

2017-02-14 14:33:43 Paul

回答