算法：最大升序子序列长度

作者: 乌鸦菌 | 来源:发表于2017-03-13 12:16 被阅读1040次

算法：最大升序子序列长度
排序算法(java实现)
子序列问题
最长上升序列
算法导论：最大子序列和
HDU-1506(单调栈)
动态规划之Longest common subsequence
300. 最长上升子序列
最长公共子序列问题总结
将数组元素循环移动p位，交换次数仅为n次

刚开始写，如有错误还望各位看官指出。若有描述不清，也请诸位提点。

导读

通过动态规划使用C语言实现求数组中最大升序（或降序）子序列长度问题。

原题

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given[10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is[2, 3, 7, 101], therefore the length is4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up:Could you improve it to O(nlogn) time complexity?

Credits:

Special thanks to@pbrotherfor adding this problem and creating all test cases.

Subscribeto see which companies asked this question.

翻译：

给出一个无序的整形数组，找出它的最大升序子序列。
举个栗子，
示例数组 arr[] = {10, 9, 2, 5, 3, 7, 101, 18}，
数组arr的最长升序子序列是 {2, 3, 7, 101}，因此长度是4。
请注意，可能有一个以上的LIS（最长上升子序列）的组合，只需要返回长度就好。
时间复杂度O(n²)前提下实现。
进阶：时间复杂度O(nlogn)前提下实现。
以下不译。

正文

以下为两种时间复杂度的C语言解法，已将log相关代码注释掉了，并粘上分步log，并简要概述思路，共同学习进步。

O(n²)

思路：
定义一个数组lis，记录以目标序列nums[0]开头，以每个元素结尾的子串的最大升序子串长度。
取出lis的最大值即为结果。
重要判断是代码中的 if (nums[i] > nums[j] && lis[j] + 1 > lis[i])。

// 此为O(n2)方法
int lengthOfLIS_01(int* nums, int numsSize) {
    if (numsSize < 2) {
        return numsSize;
    }
    int lis[numsSize];
//    printf("OriginalArray:");
//    printArray(nums, numsSize);
//    // 此for循环只是为了log美观 无意义
//    for (int i =0; i < numsSize; i++) {
//        lis[i] = 0;
//    }
    int i, j, result = 0;
    for (i = 0; i < numsSize; i++) {
        lis[i] = 1;
        for (j = 0; j < i; j++) {
            if (nums[i] > nums[j] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;
            }
        }
        result = result > lis[i] ? result : lis[i];
//        printArray(lis, numsSize);
    }
    return result;
}

O(n²) lengthOfLIS_01 的 Log（为了便于观察理解打印时隐去了值为0的元素）
此处打印的是记录以每个元素结尾的子串中最大升序子串长度的数组。

OriginalArray:10, 9, 2, 5, 3, 7,80,18, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 1,
 1, 1,
 1, 1, 1,
 1, 1, 1, 2,
 1, 1, 1, 2, 2,
 1, 1, 1, 2, 2, 3,
 1, 1, 1, 2, 2, 3, 4,
 1, 1, 1, 2, 2, 3, 4, 4,
 1, 1, 1, 2, 2, 3, 4, 4, 1,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8,
 1, 1, 1, 2, 2, 3, 4, 4, 1, 2, 3, 4, 5, 6, 7, 8, 9,
result = 9

O(nlogn)

思路：
定义数组tmp记录当前最大升序子串（∴tmp必然升序），用tmp的末位元素对比目标序列nums[1]开始的每个元素，若当前nums元素 > tmp末位元素，当前nums元素插入tmp。否则用当前nums元素替换tmp中合理位置元素即可。

// 折半(二分)查找
int binarySearch(int *array, int lenght, int key) {
    int low = 0;
    int high = lenght - 1;
    int middle;
    while (low <= high) {
        middle = low + (high - low) / 2;
        if (array[middle] > key) {
            high = middle - 1;
        } else if (array[middle] < key) {
            low = middle + 1;
        } else {
            return middle;
        }
    }
    return low;
}

// 此为O(nlog(n))方法
int lengthOfLIS_02(int* nums, int numsSize) {
    // 长度若为0或1，无须比较直接返回
    if (numsSize < 2) {
        return numsSize;
    }
    // 声明临时数组，赋值首元素，当前lenght = 1
    int tmp[numsSize], position;
//    printf("OriginalArray:");
//    printArray(nums, numsSize);
//    // 此for循环只是为了log美观 无意义
//    for (int i =0; i < numsSize; i++) {
//        tmp[i] = 0;
//    }
    tmp[0] = nums[0];
    int lenght = 1;
    // 遍历nums[1]~nums[numsSize-1]
    for (int i = 1; i < numsSize; i++) {
        // 若当前nums元素 > tmp最大元素，插入tmp，length++
        if (nums[i] > tmp[lenght - 1]) {
            tmp[lenght] = nums[i];
            lenght++;
//            printf("Part-A i=%2d len=%2d Arr:", i, lenght);
        } else {
            // 二分定位 用当前nums元素 替换 tmp中合理位置元素
            position = binarySearch(tmp, lenght, nums[i]);
            tmp[position] = nums[i];
//            printf("Part-B i=%2d pos=%2d Arr:", i, position);
        }
//        printArray(tmp, numsSize);
    }
//    printf("Finished\n");
//    printArray(tmp, numsSize);
    return lenght;
}

O(nlogn) lengthOfLIS_02 的 Log（为了便于观察理解打印时隐去了值为0的元素）

OriginalArray:10,  9,  2,  5,  3,  7, 80, 18,  1,  2,  3,  4,  5,  6,  7,  8,  9, 
Part-B i= 1 pos= 0 Arr: 9, 
Part-B i= 2 pos= 0 Arr: 2, 
Part-A i= 3 len= 2 Arr: 2,  5, 
Part-B i= 4 pos= 1 Arr: 2,  3, 
Part-A i= 5 len= 3 Arr: 2,  3,  7, 
Part-A i= 6 len= 4 Arr: 2,  3,  7, 80, 
Part-B i= 7 pos= 3 Arr: 2,  3,  7, 18, 
Part-B i= 8 pos= 0 Arr: 1,  3,  7, 18, 
Part-B i= 9 pos= 1 Arr: 1,  2,  7, 18, 
Part-B i=10 pos= 2 Arr: 1,  2,  3, 18, 
Part-B i=11 pos= 3 Arr: 1,  2,  3,  4, 
Part-A i=12 len= 5 Arr: 1,  2,  3,  4,  5, 
Part-A i=13 len= 6 Arr: 1,  2,  3,  4,  5,  6, 
Part-A i=14 len= 7 Arr: 1,  2,  3,  4,  5,  6,  7, 
Part-A i=15 len= 8 Arr: 1,  2,  3,  4,  5,  6,  7,  8, 
Part-A i=16 len= 9 Arr: 1,  2,  3,  4,  5,  6,  7,  8,  9, 
Finished
 1,  2,  3,  4,  5,  6,  7,  8,  9, 
result = 9

相关的其他函数（非重要内容可忽略）

void testCode() {
    int arr[] = {10,9,2,5,3,7,80,18,1,2,3,4,5,6,7,8,9};
//    int arr[] = {3,5,6,2,5,4,19,5,6,7,12};
//    int count = lengthOfLIS_01(arr, sizeof(arr)/sizeof(int));
    int count = lengthOfLIS_02(arr, sizeof(arr)/sizeof(int));
    printf("result = %d\n", count);
}

void printArray(int *a, int count) {
    for (int i = 0; i < count; i++) {
        if (a[i] != 0)
        printf("%2d ,",a[i]);
    }
    printf("\n");
}