微软电面试题

问题描述：

给定一个无序的数组，求至少插入多少次可以使得这个数组有序？

例如：5,1,2,3 经过一次插入 1,2,3,5

思路：其实只要保证原始数组中最长的递增的那些数字保持不动，其余的数字依次插入即可。

因此该问题转变成求最长递增序列。

　　利用数组，d[i]表示从位置0到位置i最长的递增子序列的长度。

若j<i,A[i]>A[j]，且初始d[i] < d[j]时，我们可以更新d[i]。

　　当A[i]>A[j]，找到一个最大的d[j]。d[i] =max(d[j]) + 1.

代码：

 1 int f(int a[], int n)
 2 {
 3     int *d = new int [n];
 4     int t;
 5     for(int i = 0; i < n; i++)
 6         d[i] = 0;
 7     d[0] = 1;
 8     for(int i = 1; i < n; i++)
 9     {
10         t = d[i];
11         for(int j = 0; j < i; j++)
12         {
13             if(a[i] > a[j] && d[j] > t)
14                 t = d[j];
15         }
16         d[i] = t + 1;
17     }
18     t = d[0];
19     for(int i = 1; i < n; i++)
20     {
21         if(d[i] > t)
22             t = d[i];
23     }
24     return n-t;
25 
26 }