这个也不对啊，好像不符合例题啊，就不必说通用性了啊。

问一下，不用链表用数组的思路呢

如果例子没有10呢？最后一个数是1哪最大的就是9了  但最长的子序列是 1,2,5,6,7,8。这个怎么解释呢？谢谢啦啊

你可能理解错了
二楼就明白了
不只有b[],c[]
还有d[],f[]............
所以呢见一个二维数组就能解决

误人子弟

[ 本帖最后由 encounter 于 2010-7-27 16:42 编辑 ]

弱弱地问下，为什么会出现8呢？最长单调递增子序列是什么意思？

可看作是子集
不过得满足2个条件
1不能改变顺序
2递增
最后比较一下谁最长不就行了么

郁闷回答了这么多问题
只有一人加点
很是郁闷


原来是有原因的


[ 本帖最后由 encounter 于 2010-7-27 17:06 编辑 ]

要不我给你写个

误人子弟了
又想到一个
例{1，2，5，3，4，9，7，8，6}
如果有一大数在前面，它到底要不要加入这个子序列，要看他后面有没有 多个 比他小且单调递增的数
如果有换掉这个大数，1，2，5，3，4
5则要舍弃
{1，5，6，2，3，4，}
如有多个大数在前  比他小且单调递增的数 要多于大数 个数 才能把大数换掉
这样的数列一定最长且满足条件，

#include<stdio.h>
int a[]={13, 15, 12, 28, 17, 33, 2, 29, 34, 30};
int b[20];//存放以a[i](0<=i<=a.length-1)为最后元素的最大递增子串的长度。
int num = 10;//num为a数组的长度
int k;//存放最大递增子串最后一个元素的下标

//求出b[i]中最大的值（即是最大递增子串的长度），并将其下标存在k中
int Max() {
    int temp = 0;
    for (int i = 0; i < num; i++) {
        if (b[i] > temp) {
            temp = b[i];
            k = i;
        }
    }
    return temp;
}

// 以a[i](0<=i<=a.length-1)为最后元素的最大递增子串的长度存到b[i]中
int Lis() {
    b[0] = 1;//以a[0]为最后元素的子串只有a[0]，所以长度为1.
    int k;
    for (int i = 1; i < num; i++) {
        k = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i] && k < b[j]) {
            //比较所有小于a[i]并位于a[i]前面的最大子串的长度。比如3 6 4 5，那么以5结尾的最大子串长度
            //等于：max{(小于5的元素有3,4)3的最大子串长度，4的最大子串长度}+1;
                k = b[j];
            }
        }
        b[i] = k + 1;//max{(小于5的元素有3,4)3的最大子串长度，4的最大子串长度}+1;
    }
    return Max();
}

//从大到小输出递增子串
void print(int index){
    printf("%d ",a[index]);  
    for (int i = 0; i < index; i++) {
        if (b[i] == b[index] - 1 && a[i] <= a[index]) {
            print(i);
            break;
        }
    }
}

void main(){
    printf("最大递增子串的长度为：%d\n",Lis());
    printf("最大递增子串从大到小输出为：\n");
    print(k);
}

[ 本帖最后由 linjx0123 于 2010-7-27 17:42 编辑 ]