网站所属网络,网站的性质和主办者,做文案应该关注的网站推荐,app制作免费给定一个顺序存储的线性表#xff0c;请设计一个算法查找该线性表中最长的连续递增子序列。例如#xff0c;(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数n#xff08;≤10 5 #xff09;#xff1b;第2行给出n个整数请设计一个算法查找该线性表中最长的连续递增子序列。例如(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数n≤10 5 第2行给出n个整数其间以空格分隔。
输出格式:
在一行中输出第一次出现的最长连续递增子序列数字之间用空格分隔序列结尾不能有多余空格。
输入样例
15 1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例
3 4 6 8
我的分析
先记录一下第一个序列的位置比如1 9 2 5 7 3 4 6 8 0 11 15 17 17 10中我先记下位置pos k ;(此时k0,所以第一个序列位置为0)。并设置序列长度为1len1,然后再看从数字1开始的这个序列最长能到哪里用for(;a[k]a[k1];k)中的a[k]a[k1]来判断。 若后面的数字大于当前数字则满足递增同时len;序列长度加一。例如19 , len:1-2。92,不满足递增则以第一个数字1为首的最大序列找到。 将全局变量mpos和mlen分别赋值为pos和len表示当前最长的序列的下标和长度。 之后从第2个数字开始继续循环。每次要和全局变量mpos和mlen比较修改mpos和mlen。 最后得到的是最后出现的最长的序列但不一定是第一个所以要在找一次寻找递增数列lenmlen的。 因为做的事情和之前一样所以就又在原来的函数中添加了一个判断。 if(flaglenmlen2){mpospos;}用了mlen2来保存最大长度。还用了一个标志变量flag以确保第一次调用的时候不会执行这部分。
我的代码(20分的放心用虽然这代码可能不咋地)
#include stdio.h
#define N 100000
int mlen;
int mlen2;
int flag0;
int mpos;
void find(int *a,int n);
int main ()
{int i,n;int * a;scanf(%d,n);a(int *)malloc(sizeof(int)*n);for(i0;in;i){scanf(%d,ai);}find(a,n);//printf(%d %d\n,mpos,mlen); 测试用的mlen2mlen;find(a,n);for(impos;imposmlen2-1;i){printf(%d ,a[i]);}printf(%d,a[i]);return 0;
}void find(int *a,int n){int i,k,sum,pos,max0,len;for(i0;in-1;i){ki;posk;len1;for(;a[k]a[k1];k){len;}if(flaglenmlen2){mpospos;}if(mlenlen){mlenlen;mpospos;}}}要是看不懂我写的就别看了我也隐隐觉得这想法和代码都有点渣。我再去看看别人的想法实践后再来更新。
——————————更新 ———————————
下面的这段代码和我的想法一样不过他是在函数中直接找到了并能输出第一个出现的。他是靠同时记录了序列的起始位置完成的我的没有记录结尾下标就只能再调用一次了。
来源https://blog.csdn.net/qq_36913610/article/details/82319910
#include stdio.h
#define MAXSIZE 100000
typedef struct Node{int Data[MAXSIZE];int size;
}Node, *List; /*传递结构指针效率高*/
List Read(List L);
void PrintSeq(List L);int main(void){Node node;List L node;L Read(L);PrintSeq(L);return 0;
}List Read(List L){int n, i;scanf(%d, n);L-size n;for(i0; in; i){scanf(%d, L-Data[i]);}return L;
}void PrintSeq(List L){int maxL, maxR, maxLen, l, r, len;int i;if(L-size0)return;else{maxLmaxR0;maxLen 1;}lr0;len 1;for(i1; iL-size; i){if(L-Data[i]L-Data[i-1]){r;len;}else{ /*遇到非增长点更新*/if(lenmaxLen){maxL l;maxR r;maxLen len;}lri;len 1;}}if(lenmaxLen){ /*遍历结束后再次判断以防遗漏*/maxL l;maxR r;maxLen len;}for(imaxL; imaxR; i){if(imaxL)printf(%d, L-Data[i]);elseprintf( %d, L-Data[i]);}
}
