算法引论中的一道题解决办法

算法引论中的一道题
最近在看Udi Manber的《算法引论》这本书，不过有道题没思路，贴在这请大家帮忙解决哈！！

考虑由下列数所组成的表。你的工作是删去尽可能少的数使得留下来的数以升序排列。例如除了前两个数以外删去所有的数就会得到一个升序序列，删去除第一个、第三个、第六个、第八个数以外的其他数也将得到一个升序序列（可以比前面少删除一些数）。
9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14 55
21 66 72 23 73 99 1 2 88 77 3 65 83 84 62 5 11 74 68 76 78 67 75 69 70 22
71 24 25 26


大家帮忙看看，给点思路哈！！

[解决办法]
可以认为是寻找一个最大递增序列吧，
该序列不一定是连续的
[解决办法]
做排序二叉树，得到树的层数，然后用数组的数的个数减去这个层数就能得到要删去的最小数目。
[解决办法]
我的思路：
1）从n[i](N>n[i]>=0,)开始扫描，找到以该元素开始能够构成递增序列的元素的一个数组ai；
2）计算数组大小len(i)，即为满足使序列升序的元素的个数（如果数组最大，说明删除的最少）；
3）取出下一个元素n[i+1]；
4）继续处理元素上n[i+1]，如果n[i+1]>n[i]，break，转3）;否则扫描整个序列直至完成，转2）；
5)根据得到的数组，数组最长的一个即为要保留的升序序列（去掉的最少）

在此算法基础上优化一下，效率应该不错。
[解决办法]

C# code

public static int[] maxInc(int[] numbers)        {            int[] value = null;            if (numbers != null)            {                int length = numbers.Length;                if (length == 1) value = numbers;                else if (length > 1)                {                    int[] maxValue = new int[length], maxIndex = new int[length], links = new int[length];                    maxValue[0] = numbers[0];                    maxIndex[0] = 0;                    links[0] = -1;                    int valueCount = 1;                    for (int average, end, number, index, i = 1; i < length; i++)                    {                        number = numbers[i];                        index = 0;                        end = valueCount;                        while (index < end)                        {                            if (number < maxValue[average = (index + end) >> 1]) end = average - 1;                            else index = average + 1;                        }                        if (index < valueCount && number > maxValue[index]) index++;                                                if (index == 0 || maxValue[index - 1] != number)                        {                            if (index == valueCount)                            {                                maxValue[index] = number;                                maxIndex[index] = i;                                links[i] = maxIndex[index - 1];                                valueCount++;                            }                            else if (number < maxValue[index])                            {                                maxValue[index] = number;                                maxIndex[index] = i;                                links[i] = (index == 0 ? -1 : maxIndex[index - 1]);                            }                        }                    }                    value = new int[valueCount];                    int linkIndex = maxIndex[--valueCount];                    value[valueCount] = numbers[linkIndex];                    while ((--valueCount) >= 0)                    {                        linkIndex = links[linkIndex];                        value[valueCount] = numbers[linkIndex];                    }                }            }            return value;        }
[解决办法]
给一个我写的DP方法： 
 

C/C++ code
void MaxAscendentSequence(){    int iArr[] = {2,1,3,-1,4,2,5,4};    unsigned int uNumItems = sizeof(iArr) / sizeof(*iArr);    int* pMaxLen = new int[uNumItems]; //记录以该点为结束的最大序列长度    int* pPath = new int[uNumItems]; //序列的路径    for(unsigned int i=0; i<uNumItems; ++i)    {        pMaxLen[i] = 1; //初始化，每个点也可以作为长度为1的序列        pPath[i] = -1;    }    for(unsigned int i=1; i<uNumItems; ++i) //外层循环从第二个点开始    {        for(unsigned int j=0; j<i; ++j) //内层循环遍历之前的所有点        {            if(iArr[j] < iArr[i]) //如果外层点可以接在内层点后，构成递增序列            {                if(pMaxLen[j]+1 > pMaxLen[i]) //并且新的序列长度，大于当前外层的长度                {                    pMaxLen[i] = pMaxLen[j] + 1; //更新长度，和路径                    pPath[i] = j;                }            }        }    }    unsigned int uMaxIndex;    unsigned int uMaxLen = 0;    for(unsigned int i=0; i<uNumItems; ++i) //遍历所有节点，找最大长度序列的结束点，其中记录了长度    {        if(uMaxLen < pMaxLen[i])        {            uMaxLen = pMaxLen[i];            uMaxIndex = i;        }    }    printf("Max Len: %u\n", uMaxLen); //显示最大长度    do    {        printf("%u, ", iArr[uMaxIndex]);//显示该序列，这里用递减来显示了        uMaxIndex = pPath[uMaxIndex];    }while(uMaxIndex != -1);    delete[] pPath;    delete[] pMaxLen;}
[解决办法]
探讨

引用:
引用: 
二叉排序树的方法，可以举个例子试试啊， 

就是，所有非叶子节点中，右子树深度的最大值。 
这里要求右子树节点大于根节点。 


9,5,6,10就是个反例 



9,5,6,10为什么是反例啊？ 
  
        9 
    5 
      6 
        10 
就是5，6，10为最大递增序列啊~

[解决办法]
学习中~~~
[解决办法]
C/C++ code
//lis//这里先输入要输入的数的个数,然后再输入这些数...然后会求出LIS长度...#include<iostream>#include<algorithm>#include<functional>#include<cstdio>using namespace std;int data[100005];int main(){    int size;    while (scanf("%d\n", &size) == 1)    {        //int size = sizeof(data)/sizeof(data[0]);        for (int i = 0; i < size; ++i) scanf("%d", data+i);        int len = 1;        for (int i = 1; i < size; ++i)        {            if (data[i] > data[len-1]) data[len++] = data[i];            else data[upper_bound(data, data+len, data[i])-data] = data[i];        }        //for (int i = 0; i < len; ++i) cout << data[i] << ' ';        //cout << endl;        cout << len << endl;    }    return 0;}
[解决办法]
就Longest increasing Subsequence  ( LIS ) 嘛~

用DP + BinarySearch  最快可以到O(nlogn)

Google一下有很多資料的~
[解决办法]
給個code  

輸入:
3
1 2 3  
輸出:
3

輸入:
4
2 1 4  3
輸出:
2

C/C++ code
int a[N], p[N];int binary_search(int m, int k);int main(){    int i, t, n, mlen;    scanf("%d", &n);    for(i = 1; i <= n; i++)        scanf("%d", &a[i]);    for(mlen = 0, i = 1; i <= n; i++)    {        t = binary_search(mlen+1, a[i]);        //  strictly increasing        if(p[t-1] < a[i])        {            if(mlen >= t)                p[t] = (p[t] < a[i])? p[t] : a[i];            else                mlen = t, p[t] = a[i];        }    }    printf("%d\n", mlen);    return 0;}int binary_search(int m, int k){    int begin_p = 0, end_p = m, temp;    while(begin_p < end_p)    {        temp = (begin_p + end_p) / 2;        if(p[temp] < k)            begin_p = temp + 1;        else            end_p = temp;    }    return begin_p;} 
 
[解决办法]
探讨

引用:
引用: 
引用: 
二叉排序树的方法，可以举个例子试试啊， 

就是，所有非叶子节点中，右子树深度的最大值。 
这里要求右子树节点大于根节点。 


9,5,6,10就是个反例 


9,5,6,10为什么是反例啊？ 
  
        9 
    5 
      6 
        10 
就是5，6，10为最大递增序列啊~ 


10应该在9的右边吧，这样才是排序树

[解决办法]
探讨

引用:
构造的二叉排序树不是完全的吧？ 


好像是不完全的,开始没有仔细考虑,误导楼主了. 

可以使用前插链表序列,效率要比简单双遍历省一些: 
一个链表用于装各个链表的第一个元素,节点结构中有"值","序数","下一据点指针". 
按一定原则进行处理: 
对于当前处理值: 
  1.遍历当前各个链表,得到以当前值为表头,指针指向各链表中的改值可插入的位置的下一据点元素.也就知道其序数. 
   …

[解决办法]
#include <iostream>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;

ofstream fout("res.txt");
//#define  cout  fout
const int MAX = 1000;
int arr[MAX];
int N;
int cn[MAX];
int result[MAX];
int flag [MAX];
int solve()
{
int max = 0;
int i, j;
for (i = 0; i < N; i ++)
{
cn[i] = 1;
result[i] = i;
}
for (i = 0; i < N; i ++)
{
max = 0;
for (j = 0; j <= i -1; j ++)
{
if (arr[i] > arr[j] && max < cn[j] + 1)
{
cn[i] = cn[j] + 1;
max = cn[i];
result[i] = j;
}
}
}
int k = 0;
int res = 0;
for (i  = 0; i < N; i ++)
{
if(res < cn[i])  
{
res = cn[i];
k = i;
}
}
memset(flag, 0, sizeof(flag));
flag[k] = 1;
while(k != result[k])
{
k = result[k];
flag[k] = 1;
}
for (i = 0; i < N; i ++)
{
if (flag[i] == 1)
{
cout << "(" << arr[i] << ")" << ' ';
}
else
{
cout << arr[i] << ' ';  
}
if ((i + 1) % 10 == 0)
{
cout << endl;
}
}
cout << "\n" ;
cout << "You should remove ";
cout << N - res ;
cout << " numbers. \n";
return 0;
}
int main()
{
ifstream fin("input.txt");
N = 0;
while(fin >> arr[N])
{
N ++;
}
solve();
system("pause");
return 0;
}
写了一个dp 大家看看对不对
结果：
(9) 44 (32) 12 7 42 (34) 92 (35) (37)  
(41) 8 20 27 83 (64) 61 28 39 93  
29 17 13 14 55 21 (66) (72) 23 (73)  
99 1 2 88 (77) 3 65 (83) (84) 62  
5 11 74 68 76 78 67 75 69 70  
22 71 24 25 26  
You should remove 42 numbers.  

[解决办法]
C/C++ code
#include <stdio.h> #include <string.h>char a[]={9,44,32,12,7,42,34,92,35,37,41,8,20,27,83,64,61,28,39,93,29,17,13,14,55,21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69,70,22,71,24,25,26};char b[55]={0};char c[55]={0};void myprint(){    int i;    for(i=0;i<55;i++){        if(c[i]==1) printf("%d ",a[i]);    }    printf("\n");}void main() {    int lb=0,lc=0;    int i=0,j=0;    char tmp;    for(i=0;i<55;i++){        /*选中第i个数*/        b[i]=1;        lb++;        /*找到第i个数前面的数*/        tmp=a[i];        for(j=i-1;j>=0;j--){            if(tmp>a[j]){                b[j]=1;                lb++;                tmp=a[j];            }        }                /*找到第i个数后面的数*/        tmp=a[i];        for(j=i+1;j<55;j++){            if(tmp<a[j]){                b[j]=1;                lb++;                tmp=a[j];            }        }        /*记录新的最佳结果*/        if(lb>=lc){            memcpy(c,b,sizeof(b));            lc=lb;            /*打印每次筛选出的新结果*/            myprint();        }        memset(b,0,sizeof(b));        lb=0;    }} 
 
[解决办法]
【时间复杂度更小的一种算法】

C/C++ code
#include <stdio.h> #include <string.h>char a[]={9,44,32,12,7,42,34,92,35,37,41,8,20,27,83,64,61,28,39,93,29,17,13,14,55,21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69,70,22,71,24,25,26};char b[55]={0};char c[55]={0};void myprint(){    int i;    for(i=0;i<55;i++){        if(c[i]==1) printf("%2d ",a[i]);    }    printf("\n");}void main() {    int lb=0,lc=0;    int i=0,j=0;    char tmp;    for(i=0;i<55;i++){        /*第i个数已经在当前最优结果中，所以跳过此次筛选*/        if(c[i]==1) continue;        /*选中第i个数*/        b[i]=1;        lb++;        /*找到第i个数前面的数*/        tmp=a[i];        for(j=i-1;j>=0;j--){            if(tmp>a[j]){                b[j]=1;                lb++;                tmp=a[j];            }        }                /*找到第i个数后面的数*/        tmp=a[i];        for(j=i+1;j<55;j++){            if(tmp<a[j]){                b[j]=1;                lb++;                tmp=a[j];            }        }        /*记录新的最佳结果*/        if(lb>=lc){            memcpy(c,b,sizeof(b));            lc=lb;            /*打印每次筛选出的新结果*/            myprint();        }        memset(b,0,sizeof(b));        lb=0;    }}
[解决办法]
c[0]=1;
c[i]=max(c[j]|a[j]<a[i],j<i)+1

要删除的序列不是唯一的，
如下所示第8～13是固定的，但第7个就不是固定的了，
其中一个结果同73楼
a[0]~a[54]
9,44,32,12,7,42,34,92,35,37,
41,8,20,27,83,64,61,28,39,93,
29,17,13,14,55,21,66,72,23,73,
99,1,2,88,77,3,65,83,84,62,
5,11,74,68,76,78,67,75,69,70,
22,71,24,25,26
c[0]~c[54]
1,2,2,2,1,3,3,4,4,5,
6,2,3,4,7,7,7,5,6,8,
6,3,3,4,7,5,8,9,6,10,
11,1,2,11,11,3,8,12,13,8,
4,5,11,9,11,12,9,11,10,11,
6,12,7,8,9

应该是这样了
我写程序太差了～
[解决办法]
不好意思，写了个小程序才发现有的地方又弄错了，好多种组合啊
4,5,11,9,11,12,9,11,10,11,应该是4,5,11,9,12,13,9,11,10,11,  
c[0]~c[54]  
1,2,2,2,1,3,3,4,4,5,  
6,2,3,4,7,7,7,5,6,8,  
6,3,3,4,7,5,8,9,6,10,  
11,1,2,11,11,3,8,12,13,8,  
4,5,11,9,12,13,9,11,10,11,  
6,12,7,8,9

#include <stdio.h>  
#include <string.h>

char a[]={9,44,32,12,7,42,34,92,35,37,41,8,20,27,83,64,61,28,39,93,29,17,13,14,55,
21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69,70,22,
71,24,25,26};

char R[55] = {1};
void main()  
{
for(int i=1; i<55; i++){
int tmp = 0;
for(int j=0; j<i; j++){
if(a[j]<a[i]){
tmp = tmp>R[j]?tmp:R[j];
}
}
R[i] = (tmp+1);
}
for(i=0; i<55; i++){
if(i!=0 && i%10 == 0)
printf("\n");
       printf("%2d, ",R[i]);
   }
}