能否扩展O(NlogN) 的LIS解法使之解决这一问题
  • 板块学术版
  • 楼主MoyunAllgorithm
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/10/27 17:40
  • 上次更新2023/11/2 11:13:18
查看原帖
能否扩展O(NlogN) 的LIS解法使之解决这一问题
378706
MoyunAllgorithm楼主2023/10/27 17:40

求最长的包含原始序列首个元素,且自己的第 ii 个元素和第 i−1i-1 个元素的差值 ≤x \le x 的最长子序列。

也就是找到 i1<i2<⋯<imi_1 < i_2 < \cdots <i_m,满足 i1=1i_1=1 且 a(ij)≥a(ij+1)+xa(i_j) \ge a_(i_{j+1}) +x 的最大的 mm。

能否适当修改 O(Nlog⁡N)O(N \log N) 的 LIS 求解算法解决该问题?注意到这时作为答案的子序列可能不是单调不增的。

2023/10/27 17:40
加载中...