java - 对的最大长度(按升序)

Question

<分区>

Answer 1

这是正确的。这是一个证明:

让s1, s2, ..., sl是你的算法找到的对和i1, i2, ..., ik是最优解。

我们有:

l == k => your algorithm is obviously correct, since it's clear that
          it doesn't produce invalid solutions;

l > k => this would contradict our hypothesis that i1, ..., ik is optimal,
         so it makes no sense to bother with this;

l < k => this would mean that your algorithm is wrong. 
         Let's assume this is the case.

假设i1 != s1 .在这种情况下，我们可以替换 i1与 s1在最佳解决方案中，因为 s1是完成时间最短的一对。所以s1, i2, ..., ik仍然是最优解。

让t <= l是 st != it 的第一个索引.因此，s1, s2, ..., s[t-1], it, ...是最优解。我们可以替换 it与 st因为:

• st不是第一个 t-1 的一部分最佳解决方案的要素；
• st不属于 i[t+1], ..., ik .如果是，那就意味着 st在 it 之后开始完成，这将与算法选择 st 的方式相矛盾.

因此，继续以这种方式，我们的最佳解决方案是 s1, s2, ..., sl, ..., ik .这意味着可以在 sl 之后添加更多对, 但这与算法的工作方式相矛盾，所以我们有 l = k , 算法正确。