最長的子序列，其元素構成一組遞增整數

查找數組中最長的連續子序列的長度，其中的元素構成一組連續增加的整數。輸入文件包含數字n（數組中的元素數），後跟整數n。
示例輸入 - 10 1 6 4 5 2 3 8 10 7 7
示例輸出-6（1 6 4 5 2 3，因爲它們使集合1 2 3 4 5 6）。
我能夠編寫滿足0<n<5000的算法，但爲了獲得100個點，該算法必須爲0<=n<=50000工作。最長的子序列，其元素構成一組遞增整數

來源

2017-04-14 David Asryan

或許，如果你發佈一些代碼來顯示你已經嘗試了什麼，人們可能沒有解決這一問題。（雖然，因爲你要求更高效的算法，所以我不是你可以提供的技術比你已經擁有的更多...） –

這樣的事情呢？按降序排列數組元素，每個元素以其索引範圍作爲局部最大值（例如，A[0] = 10應該是數組索引的最大值，[0, 10]，而A[3] = 4應該是數組索引的局部最大值，[3,3]。現在遍歷此列表，找到最長，連續下降的序列，其中的指數範圍都包含在初始範圍。

10 1 6 4 5 2 3 8 10 7 7 
=> 10, [ 0,10] 
    8, [ 1, 7] 
    7, [ 9,10] 
    6, [ 1, 6] <-- 
    5, [ 3, 6] | ranges 
    4, [ 3, 3] | all 
    3, [ 5, 6] | contained 
    2, [ 5, 5] | in [1,6] 
    1, [ 1, 1] <--

來源

2017-04-17 04:39:29

嗯，確實是一個非常好的解決方案，但有反覆出現的元素確實傷害了算法rithm。例如，如果在5到達另一個5之後，算法會變得非常模糊。或者在更壞的情況下，如果數組是這樣的 - 1 5 4 2 3 7 1 5 4 2 3？ –

@DavidAsryan感謝您的評論。按照其開始索引排列數組中的每組重複項。任何作爲連續任期候選人的副本都是（1）該條款之後的下一個較低的數字，以及（2）由於是下一個較低的數字，必須共享相同的開始和結束（如果他們在同一側）或者具有相互排斥的索引範圍作爲局部最大值（例如，在你的例子中，5的值作爲連續7的候選項，例如'1 5 4 2 3 7 1 5 4 2 3'）。 –

@DavidAsryan你也可以澄清一下這樣的解決方案：'1 1 2 2 3 3 4 4'。 –

最長的子序列，其元素構成一組遞增整數

回答

相關問題