求出部分有序数组中的最大子数组(第一次出现)的长度及位置 (c++实现)
在复习数据结构是,看到书中有这么一个题目:
求出部分有序数组中的最大子数组(第一次出现)的长度及位置
然后就简单的实现了下,难免有疏漏之处,还望见谅和指出,在此谢过
在CodeBlocks中编译通过,下面贴出代码:
//找出部分有序的数组中连续有序最长的子数组 #include <iostream> using namespace std; void lenth(int a[], int n, int *max_len, int *pos) { *max_len = 0; //保存最大子数组的长度,并返回 *pos = 0; //保存最大子数组的第一个元素出现的位置 int i=0, j=0, len=0; for(i=0; i<n-1; i++) { if(a[i] < a[i+1]) { ++len; if(*max_len < len) { *max_len = len; *pos = i; } } else //一旦出现逆序的,len置0 { len = 0; } } *max_len = *max_len + 1; // +1 是因为上面是a[i] < a[i+1] *pos = *pos - *max_len + 2; //+2 是因为*pos开始保存的是最大子数组的最后元素的位置 } int main() { int a[] = {2,5,6,1,3,8,9}; int n = sizeof(a)/sizeof(a[0]); int max_len, pos; lenth(a, n, &max_len, &pos); cout << max_len <<" " << pos << endl; return 0; }
声明:该文观点仅代表作者本人,牛骨文系教育信息发布平台,牛骨文仅提供信息存储空间服务。
- 上一篇: 无序数组中是否包含某一个要找的元素的几种方法
- 下一篇: 从有序数组中查找某个值(二分)