定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
时间: 2023-06-05 20:48:01 浏览: 108
算法步骤如下:
1. 定义两个变量:start表示当前递增子序列的起始位置,end表示当前递增子序列的结束位置。
2. 定义两个变量:maxStart表示最长递增子序列的起始位置,maxEnd表示最长递增子序列的结束位置。
3. 遍历线性表,如果当前元素大于等于前一个元素,则将end加1,否则将start和end都设置为当前位置。
4. 每次更新end时,判断当前递增子序列的长度是否大于最长递增子序列的长度,如果是,则更新maxStart和maxEnd。
5. 遍历结束后,根据maxStart和maxEnd输出最长递增子序列。
算法实现如下:
```
void findLongestIncreasingSubsequence(int a[], int n) {
int start = 0, end = 0, maxStart = 0, maxEnd = 0;
for (int i = 1; i < n; i++) {
if (a[i] >= a[i-1]) {
end = i;
} else {
start = i;
end = i;
}
if (end - start > maxEnd - maxStart) {
maxStart = start;
maxEnd = end;
}
}
printf("最长递增子序列为:");
for (int i = maxStart; i <= maxEnd; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
```
使用示例:
```
int a[] = {1, 9, 2, 5, 7, 3, 4, 6, 8, 0};
int n = sizeof(a) / sizeof(int);
findLongestIncreasingSubsequence(a, n);
```
输出结果:
```
最长递增子序列为:3 4 6 8
```
阅读全文