问题描述：
在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤ i ≤n,是｛1,2,…,n｝的一个排列。导线(I, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n,第i条连线和第j条连线相交的充要条件是π(i)> π(j).
π（i）=｛8，7，4，2，5，1，9，3，10，6｝
在制作电路板时，要求将这n条连线分布到若干绝缘层上。换句话说，**这个问题是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线（不相交）。**该问题要求确定导线集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不相交子集。
算法思路：
对于上接线柱i1<i2<i3<…<ik来说。它们与下接线柱f(i)的连线之间互不相交的充要条件是：
f(i1)<f(i2)<…<f(ik)。
因为对于i1<i2如果f(i1)>f(i2)则它们一定相交.
!!!:因此，我可以将这个电路布线问题，转化为这样的问题：
已知有一个{1,2,3,…,n}的排列，将其拆分为k个子排列，并且每个子排列都是严格递增的，求子排列的最大元素个数。
例如：排列 8，7，4，2，5，1，9，3，10，6可以拆分成五个子排列{4,5,9,10}{8}{7}{2,3,6}{1} 。
它最大的元素个数是4。
排列 1,2,3,4,5,6,7,8,9,10它是递增的，所以无需拆分，最大元素个数是10。
算法实现：
对于排列8，7，4，2，5，1，9，3，10，6。
先记录第一个数8，向后扫描，如果有大于8的，count++，则可以产生一个子排列{8,9}，继续扫描产生子排列{8,9,10}。扫描完毕后姑且认为子排列最大元素是3个。第二次以7向后扫描，只要扫描到比它大的，就将产生一个子排列，继续向后扫描，扫描结束后，得到排列是{7,9,10}。个数是3，与之前的比较。第三次以4开始扫描，。。。依次下去至扫描结束。
此算法与动态规划算法时间复杂度一样，都是O(n²)，但此算法更好理解。
#include <iostream>using namespace std;const int N = 10;int connected(int pai[], int max) {for (int i = 0; i < N; i++) {int count = 1;int t = pai[i];for (int j = i + 1; j < N; j++) {if (pai[j] > t) {count++;t = pai[j];if (max < count) {max = count;}}}}return max;}int main() {int max = 0;int pai[] = {8, 7, 4, 2, 5, 1, 9, 3, 10, 6};cout << "对应连接的接线柱是：" << endl;for (int i = 0; i < N; i++) {cout << pai[i] << " ";}cout << endl << "电路布线最大不相交连线数目是：" << connected(pai, max);return 0;}
递归实现完整代码：
#include <iostream>using namespace std;const int N = 10;int sub[] = {8, 7, 4, 2, 5, 1, 9, 3, 10, 6};int connected(int maxElement, int e = 1, int count = 1) {if (e == N - 1) {if (sub[e] > maxElement) count++;return count;} else {if (sub[e] > maxElement) {count++;maxElement = sub[e]++;}return connected(maxElement, e + 1, count);}}int main() {int max = 0, t;for (int i = 0; i < N; i++)if ((t = connected(sub[i])) > max) max = t;cout << "电路布线最大不相交连线数目是：" << max;return 0;}
