精华内容
下载资源
问答
  • 最长连续递增子序列

    2018-09-17 16:03:07
    最长连续递增子序列 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10 ​5 ...

    最长连续递增子序列

    给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(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

    #include <stdio.h>
    int main()
    {
        int i,n,Thissum=1,Maxsum=1,Maxi=0;
        int str[1000000];
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d",&str[i]);
        }
        for(i=0;i<n;i++){
            if(str[i+1]>str[i]) Thissum++;
            if(Thissum>Maxsum){
                    Maxsum=Thissum;
                    Maxi=i+1;
            }
            else if(str[i+1]<str[i]) Thissum=1;
        }
        for(i=Maxi-Maxsum+1;i<Maxi;i++){
            printf("%d ",str[i]);
        }
        printf("%d",str[Maxi]);
        return 0;
    }
    
    展开全文
  • 最长连续递增子序列长度和最长不连续递增子序列长度 1.最长连续递增子序列 例如:Array[6] = {1,5,2,4,3,8} 其最长连续递增子序列就2,4或3,8,最长长度为2 设数组dp[i],表示以i为结尾的最长连续子序列长度,...

    最长连续递增子序列长度和最长不连续递增子序列长度

    1.最长连续递增子序列
    例如:Array[6] = {1,5,2,4,3,8}
    其最长连续递增子序列就2,4或3,8,最长长度为2
    设数组dp[i],表示以i为结尾的最长连续子序列长度,即上述数组的dp数组即为
    dp[6] = {1,1,1,2,1,2}
    代码如下

    #include<iostream>
    using namespace std;
    int main(){
        int Array[6] = {1,5,2,4,3,8};
        int dp[6];
        dp[0] = 1;
        for(int i=1;i<6;i++){
            dp[i] = 1;
            if(Array[i] > Array[i-1]){
                dp[i] = dp[i-1] + 1;
            }
        }
        for(int i=0;i<6;i++)
        	cout<<dp[i]<<" ";
    }
    
    

    2.最长不连续递增子序列
    例如:Array[6] = {1,5,2,4,3,8}
    其最长连续递增子序列就1,2,418或1,2,3,8,最长长度为4
    设数组dp[i],表示以i为结尾的最长不连续子序列长度,即上述数组的dp数组即为
    dp[6] = {1,2,2,3,3,4}
    代码如下

    #include<iostream>
    using namespace std;
    int main(){
        int Array[10] = {1,5,2,4,3,8,7,2,9,10};
        int dp[10];
        dp[0]=1;
        for(int i=1;i<10;i++){
            dp[i] = 1;
            for(int j=i-1;j>=0;j--){
                if(Array[i]>Array[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        for(int i=0;i<10;i++)
            cout<<dp[i]<<" ";
    }
    
    
    展开全文
  • 习题3.4 最长连续递增子序列 存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10 ​5 ​​ );...

    习题3.4 最长连续递增子序列
    存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(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

    #include<stdio.h>
    #include<string.h>
    int main()
    {
    int i,n,max,max1=0;
    int count=0;
    scanf("%d",&n);
    int a[100009]={0};

    for(i=0;i<n;i++)
    {
    	scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++)
    

    {
    //只有一个时
    if(i==0)
    {
    count=1;
    max=1;
    max1=i;
    }
    //需要一个用来记最大的个数
    else if((a[i]-a[i-1])>0)
    {
    count++;
    if(count>max)
    {
    max=count;
    max1=i;///因为循环可以得到最长连续递增序列的最后一个下标
    }
    }
    else if((a[i]-a[i-1])<0){
    count=1;//因为i=0,才让count=1;
    }
    }
    for(i=max1-max+1;i<=max1;i++)
    {
    printf("%d",a[i]);
    if(i!=max1)
    printf(" “);
    else
    printf(”\n");
    }
    return 0;

    }

    展开全文
  • 7-2最长连续递增子序列 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10​5...

    7-2 最长连续递增子序列

    给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(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
    

    解:

    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    typedef int ElemType;
    
    typedef struct{
        ElemType *elem;
        int length;
        int listsize;
    }SqList;
    
    typedef struct{
        int length;
        ElemType *p_start;
        ElemType *p_end;
    }ContinuousIncSub;
    void GetLongestContinuousIncSub(SqList &L);
    int main()
    {
        //freopen("data.txt","r",stdin);
        int n;
        scanf("%d",&n);
        SqList L;
        L.elem=(ElemType*)calloc(n,sizeof(ElemType));
        if(!L.elem) exit(-1);
        L.listsize=n;
        L.length=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d",L.elem+i);
            ++L.length;
        }
        //求最长连续递增子序列
        GetLongestContinuousIncSub(L);
        //输出
        for(int i=0;i<L.length;++i)
        {
            if(i==0)
                printf("%d",*(L.elem));
            else
                printf(" %d",*(L.elem+i));
        }
        return 0;
    }
    //求最长连续递增子序列的函数
    void GetLongestContinuousIncSub(SqList &L)
    {
        if(L.length==1)
            return;
        ContinuousIncSub cur_IncSub,max_IncSub;
        //初始化
        max_IncSub.p_start=max_IncSub.p_end=NULL;
        max_IncSub.length=0;
        cur_IncSub.p_start=cur_IncSub.p_end=NULL;
        cur_IncSub.length=0;
    
        int *p1=L.elem;
        int *p2=L.elem+1;
        cur_IncSub.p_start=p1;
        cur_IncSub.length=1;
        while(p1<L.elem+L.length&&p2<L.elem+L.length)
        {
            if(*p2>*(p2-1))
            {
                cur_IncSub.length++;
                ++p2;
            }
            if(p2>=L.elem+L.length)
            {
                cur_IncSub.p_end=p2;
                if(cur_IncSub.length>max_IncSub.length)
                {
                    max_IncSub.p_start=cur_IncSub.p_start;
                    max_IncSub.p_end=cur_IncSub.p_end;
                    max_IncSub.length=cur_IncSub.length;
                }
                break;
            }
            if(p2<L.elem+L.length&&*p2<=*(p2-1))
            {
                cur_IncSub.p_end=p2;
                if(cur_IncSub.length>max_IncSub.length)
                {
                    max_IncSub.p_start=cur_IncSub.p_start;
                    max_IncSub.p_end=cur_IncSub.p_end;
                    max_IncSub.length=cur_IncSub.length;
                }
                p1=p2;
                ++p2;
                cur_IncSub.p_start=p1;
                cur_IncSub.length=1;
            }
        }
        L.elem=(ElemType*)malloc(sizeof(ElemType)*max_IncSub.length);
        if(!L.elem) exit(-1);
        L.listsize=max_IncSub.length;
        L.length=0;
        for(int i=0;max_IncSub.p_start<max_IncSub.p_end;++max_IncSub.p_start,++i)
        {
            *(L.elem+i)=*(max_IncSub.p_start);
            ++L.length;
        }
    }
    

    总结:

    对于最长连续递增子序列这个题,要注意考虑一些特殊情况,比如说,当序列长度为一时,程序应该输出什么,以及当序列中元素全部相同时,应该输出什么。还有就是,此题如果用指针的话,要注意对边界的控制,防止指针越界访问非法的内存。

     

    展开全文
  • 7-1 最长连续递增子序列 (20分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,964
精华内容 3,985
关键字:

最长连续递增子序列