求解最长单调递增子串

发表于 | 分类于 | | 阅读次数:

求解最长递增子串可分为两种情况，即子串连续或非连续。
例如，对于整数串{1,3,5,1,-1,4,5,3,1,8,3,4,6,2,4,6,7,8,6,4}
其连续递增子串为{2,4,6,7,8}，非连续递增子串为{ {-1},{1},{2,4,6,7,8}}

连续递增子串的求解思路：

采用动态规划思想，令
lengthOfSubList[k]表示子串{list[0]…list[k]}中最长的连续递增子串长度
lengthOfSubListIncludeK[k]表示子串{list[0]…list[k]}中以list[k]结尾的最长连续递增子串长度
indexOfLastElement[k]表示子串{list[0]…list[k]}中最长的连续递增子串的最后一个元素的位置
则
lengthOfSubListIncludeK[k] =
lengthOfSubListIncludeK[k-1]+1,list[k]>=list[k-1]
1,list[k]<list[k-1]
lengthOfSubList[k] = max(lengthOfSubListIncludeK[k],lengthOfSubList[k-1])
indexOfLastElement[k] =
k,lengthOfSubListIncludeK[k]>lengthOfSubList[k-1]
indexOfLastElement[k-1],lengthOfSubListIncludeK[k]<=lengthOfSubList[k-1]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdlib.h> 
#include <stdio.h> 

void MaxIncrementSubList(int list[],int length) 
{ 
    //lengthOfSubList[k]表示子串{list[0]...list[k]}中最长的连续递增子串长度 
    //lengthOfSubListIncludeK[k]表示子串{list[0]...list[k]}中以list[k]结尾的最长连续递增子串长度 
    int* lengthOfSubList = (int*)malloc(sizeof(int)*length); 
    int* lengthOfSubListIncludeK = (int*)malloc(sizeof(int)*length); 
    int* indexOfLastElement = (int*)malloc(sizeof(int)*length); 
    int i; 
    //初始化 
    for (i=0;i<length;i++) 
    { 
        lengthOfSubList[i] = 1; 
        lengthOfSubListIncludeK[i] = 1;  
        indexOfLastElement[i] = i;   
    } 
    //按照动态规划思想，计算lengthOfSubList[k]和lengthOfSubListIncludeK[k] 
    for (i=1;i<length;i++) 
    { 
        if (list[i]>=list[i-1]) lengthOfSubListIncludeK[i] = lengthOfSubListIncludeK[i-1]+1; 
        else lengthOfSubListIncludeK[i] = 1; 
        if (lengthOfSubListIncludeK[i]>lengthOfSubList[i-1]) 
        { 
            lengthOfSubList[i] = lengthOfSubListIncludeK[i]; 
            indexOfLastElement[i] = i; 
        } 
        else 
        { 
            lengthOfSubList[i] = lengthOfSubList[i-1]; 
            indexOfLastElement[i] = indexOfLastElement[i-1]; 
        } 
    } 
    //逆序输出最长连续递增子串 
    printf("longest sub list is:\n"); 
    int idx = indexOfLastElement[length-1]; 
    while (list[idx]>=list[idx-1]) 
    { 
        printf("[%d]=%d ",idx,list[idx]); 
        idx--; 
    } 
    printf("[%d]=%d ",idx,list[idx]); 
} 

int main() 
{ 
    int list[20] = {1,3,5,1,-1,4,5,3,1,8,3,4,6,2,4,6,7,8,6,4}; 
    MaxIncrementSubList(list,20); 
    int a; 
    scanf("%d",&a); 
    return 0; 
}

214216131

非连续递增子串的求解思路：

采用动态规划思想，令
lengthOfSubList[k]表示子串{list[0]…list[k]}中最长的非连续递增子串长度
lengthOfSubListIncludeK[k]表示子串{list[0]…list[k]}中以list[k]结尾的最长非连续递增子串长度
indexOfLastElement[k]表示子串{list[0]…list[k]}中最长的非连续递增子串的最后一个元素的位置
则
lengthOfSubListIncludeK[k] = max(lengthOfSubListIncludeK[i]+1, list[k]>=list[i], i=0..k-1)
lengthOfSubList[k] = max(lengthOfSubListIncludeK[k],lengthOfSubList[k-1])
indexOfLastElement[k] =
k, lengthOfSubListIncludeK[k]>lengthOfSubList[k-1]
indexOfLastElement[k-1],lengthOfSubListIncludeK[k]<=lengthOfSubList[k-1]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdlib.h> 
#include <stdio.h> 

void MaxIncrementSubList(int list[],int length) 
{ 
    //lengthOfSubList[k]表示子串{list[0]...list[k]}中最长的非连续递增子串长度  
    //lengthOfSubListIncludeK[k]表示子串{list[0]...list[k]}中以list[k]结尾的最长非连续递增子串长度  
    int* lengthOfSubList = (int*)malloc(sizeof(int)*length); 
    int* lengthOfSubListIncludeK = (int*)malloc(sizeof(int)*length); 
    int* indexOfLastElement = (int*)malloc(sizeof(int)*length); 
    int i,j,max; 
    //初始化 
    for (i=0;i<length;i++) 
    { 
        lengthOfSubList[i] = 1; 
        lengthOfSubListIncludeK[i] = 1;  
        indexOfLastElement[i] = i;   
    } 
    //按照动态规划思想，计算lengthOfSubList[k]和lengthOfSubListIncludeK[k] 
    for (i=1;i<length;i++) 
    { 
        max = lengthOfSubListIncludeK[i]; 
        for (j=0;j<i;j++) 
        { 
            if (list[i]>list[j]) 
            { 
                lengthOfSubListIncludeK[i] = lengthOfSubListIncludeK[j]+1; 
                if (max<lengthOfSubListIncludeK[i]) max = lengthOfSubListIncludeK[i]; 
            } 
        } 
        lengthOfSubListIncludeK[i] = max; 
        if (lengthOfSubListIncludeK[i]>lengthOfSubList[i-1]) 
        { 
            lengthOfSubList[i] = lengthOfSubListIncludeK[i]; 
            indexOfLastElement[i] = i; 
        } 
        else 
        { 
            lengthOfSubList[i] = lengthOfSubList[i-1]; 
            indexOfLastElement[i] = indexOfLastElement[i-1]; 
        } 
    } 
    //逆序输出最长非连续递增子串  
    printf("longest sub list is:\n"); 
    int idx = indexOfLastElement[length-1]; 
    int tmp = list[idx]; 
    for (i=idx;i>=0;i--) 
    { 
        if (list[i]<=tmp) 
        { 
            printf("[%d]=%d ",i,list[i]); 
            tmp = list[i]; 
        } 
    } 
} 

int main() 
{ 
    int list[20] = {1,3,5,1,-1,4,5,3,1,8,3,4,6,2,4,6,7,8,6,4}; 
    MaxIncrementSubList(list,20); 
    int a; 
    scanf("%d",&a); 
    return 0; 
}

214104722