文档介绍：问题描述如下：
，用最简单的算法找出重合长度最长的线段。比如线段A
（1,5）、B （2,8）、C （3,9）,则B和C的重合长度最长，（3,8）
这个问题可以转换成一个动态规划问题：
比如我们想求Sn（Sn表示从求从第一个segment开始，总共有n个元素的子问题，求这个 子问题的最大重合线段。），首先我们要证明这是一个动态规划问题：
我们要求Sn问题的最大重合线段，那么它只有可能有两种来源：
（1） Sn-1问题的最大重合线段，即Sn的最大重合线段出自前n-1个线段；
（2） 第n个线段Segment[n-1]（注意：我是从0开始计数的，所以下标为n-1的就是第n 个线段）和前n-1个线段的重合线段中最长的那一个。
所以，问题的解法如下：
（1） 首先按照所有线段的end值对所有线段进行排序；
（2） 递归的从后往前求解，比如求Sn的最大重合线段，先通过递归求出Sn-1的最大重合 线段（tmpMaxSeg）,再求出Segment[n-1闲前n-1个线段的重合线段中最长的那一个 （currMaxSeg）,比较tmpMaxSeg和currMaxSeg的长度，选出最长的作为Sn的返回值。
（3） 注意：递归出口： size==2时，只有两个线段，通过简单比较就可以得出最大覆盖线 段；
至于这块儿：是为了应对原本传入的线段数组的大小小于等于1的情况，算是边界条件处 理了，不是递归的出口。
假如传入数组大小为3,递归执行到数组大小为2时就可以返回了。
[cpp] view plaincopyprint?
1. if(NULL == Segment)
3・ cerr << "the segment array is NULL" << endl;
return -1;
}
else if(1 == size)
{
maxSeg = Segment[0];
return ・;
}
实现代码如下:
[cpp] view plaincopyprint?
1・
#inelude <iostream>
2・
#inelude <cstdlib>
3・
#inelude <algorithm>
4・
const int LEN = 3;
5・
6・
using namespace std;
7・
8.
struet segment
9・
{
10.
int start;
11.
int end;
12.
｝；
13.
14.
// assume <
15.
segment commonSeg(const segment & a, const segment & b)
16.
{
17.
segment CommonSeg;
18.
if( < )
19.
{
20.
= 0;
21.
= 0;
22.
}
= ;
= b・start;
}
return C