2013年08月16日

最长递增子序列


最长递增子序列是一个很老的问题了,上镜频率特别高,不少面试题是由它变化而来,所以将这个问题贴出来,也是自己练练手。题目描述如下:

存在一个序列A[9] = {2,1,5,3,6,4,8,9,7},那么其最长递增子序列便是{2,3,4,8,9},长度为5。现在的要求就是查找这个最长递增子序列

分析

这篇博客中给出了三种解法,首先是动态规划,其次是排序结合最长公共子序列,最后是动态规划另加二分查找。

第一种动态规划是常用的动态规划的思想,找出最优子结构,列出递归方程,然后求解。第二种方法是,首先将序列排序,然后得到一个有序的新序列,然后和原来的序列求解最长公共序列。

第三种方法则是在查找最长递增子序列的过程中,时刻记录已经查找到的长度为N的递增子序列的最小末尾,每处理一个元素,动态更新此记录。

方法三

对于题目中给出的数组A[9],我们使用方法三的过程如下,使用一个辅助存储空间,B[9],然后开始遍历数组A,首先是元素2,那么此时长度为1的递增子序列,最小末尾是2,那么B[1] = 2,下一个元素是1,1大于2,那么现在长度为1的递增子序列的最小末尾应该是1了,那么B[1] = 1,接着下一个元素是5,5比1大,则现在长度为2的递增子序列的最小末尾是5了,则B[2] = 5,下一个元素是3,3比5小,却比1大,所以长度为2的递增子序列的最小末尾是3,那么B[2] = 3, 接着下一个元素是6,那么6比3大,所以,长度为3的递增子序列的最小末尾是6,那么B[3]=6。依次类推,我们在处理元素3时,经过了一次比较,其中就用来二分查找来加快速度。

代码如下:

int longestIncreasingSubsequence(int* array, int len){
    if(array == NULL || len <=0 )
        return 0;
    int *lis = new int[len];
    lis[0] = array[0];
    int i,lis_len = 1;
    int left, right, middle;
    for(i = 1; i < len; i++){
        if(array[i] > lis[lis_len - 1])
            lis[lis_len++] = array[i];
        else{ //binary search first data which is big than array[i]
            left = 0;
            right = lis_len - 1;
            while(left < right){
                middle = (left + right) / 2;
                if(lis[middle] > array[i])
                    right = middle;
                else
                    left = middle + 1;
            }
            lis[left] = array[i];
        }
    }
    delete [] lis; 
    return lis_len;
}

方法二

第二种方法则是快排和最长公共子序列问题的一个结合,首先快排,然后动态规划来求解最长公共子序列。其中最长公共子序列有一些列类似的问题,譬如最长公共子串等等。

快速排序的代码如下:

int partition(int *array, int left, int right){
    if(array == NULL || left <= 0 || right <=0 || left > right)
        return;
    int key = array[left];
    while(left < right){
        while(right > left && array[right] >= key)
            right--;
        array[left] = array[right];
        while(left < right && array[left] <= key)
            left++;
        array[right] = array[left];
    }
    array[left] = key;
    return left;
}

void quickSort(int *array,int left, int right){
    if(array == NULL || left <= 0 || right <=0 || left > right)
        return;
    if(left < right){
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot -1);
        quickSort(array,pivot+1,right);
    }
}

寻找最长公共子串的代码如下:

int lcs(int *array,int *sorted, int len, int **state){
    if(array == NULL || state == NULL || len <=0)
        return 0;
    int i = 0, j = 0;
    for(i = 0; i < len; i++){
        if(array[i] == sorted[0])
            state[i][0] = 1;
        else
            state[i][0] = 0;
    }

    for(i = 0; i < len; i++){
        if(array[0] == sorted[i])
            state[0][i] = 1;
        else
            state[0][i] = 0;
    }

    for(i = 1; i < len; i++){
        for(j = 1; j < len; j++){
            if(array[i] == sorted[j]){
                state[i][j] = state[i-1][j-1] + 1;
            }else if(state[i-1][j] > state[i][j-1]){
                state[i][j] = state[i-1][j];
            }else{
                state[i][j] = state[i][j-1];
            }
        }
    }
    return state[len-1][len-1];
}

寻找最长公共子串使用的是动态规划方法,其递归方程是:

当A[i] == B[j]时, F[i][j] = F[i-1][j-1] + 1 当A[i] != B[j]时,F[i][j]= max{F[i-1][j],F[i][j-1]}

前一篇: Unix网络io模型 后一篇: 旋转图片