6-05 2,253 views
求解最长递增子串可分为两种情况，即子串连续或非连续。
例如，对于整数串{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; } |
非连续递增子串的求解思路：
采用动态规划思想，令
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; } |
版权属于: 我爱我家
转载时必须以链接形式注明原始出处及本声明。