【林中雪舟】找出重合长度最长线段

题目描述如下: (对于这类算法题,需要将《算法导论》再学习一遍,同时,将书中所列出的引文也要重新学习一遍)

在一维坐标轴上存在许多条线段,用最简单的算法找出重合长度最长的线段。比如线段A(1,5)、B(2,8)、C(3,9),则B和C的重合长度最长,为5.返回(3,8)

1, 第一种方法是使用动态规划的做法,假设已知有n个点,相应的最长长度为L(n), L(0) = 0; L(1) = 0; 对于n>2, 则有

            L(n) = max ( L(n-1), max_dist(An, Aj) )

   在 HERE 给出的代码没有考虑 a[i].start < a[k].start  AND  a[k].end < a[i].end (k > i) 的情形;

  想起另外一题,就是说,如果要计算得不是各个点之间的最大距离,而是计算两个端点,他们能够覆盖最多的其余点数; 

 这个算法的时间复杂度是 O(n^2)的,所以这样的做法,其实就是从后向前进行遍历搜索,即,点An 与 点Ak (0<=k < n)逐一比较进行计算,比较的次数为:

    对于有n+1个点, n + (n-1) + (n-2) + ... + 1 = 1/ 2 * n * (n+1) 

相关代码实现:

原文地址:https://www.cnblogs.com/superniaoren/p/3348270.html