精华内容
下载资源
问答
  • 最长连续递增子序列长度和最长连续递增子序列长度
    千次阅读
    2019-03-16 15:15:07

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

    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]<<" ";
    }
    
    
    更多相关内容
  • 主要介绍了C语言实现最长递增子序列问题的解决方法,采用递归的方法解决该问题,是非常经典的一类算法,需要的朋友可以参考下
  • 案例3-1.2 最长连续递增子序列 (20 分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正...

    案例3-1.2 最长连续递增子序列 (20 分)
    给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(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
    结尾无空行

    思路:

    求最长连续递增序列,那么必然满足条件“递增”,也就是a[j] > a[j-1]
    由题目可知最后的输出是一段递增序列,所以有效数据如何保存很关键,可以新建数组保存或者是记录递增序列的起始位置。
    这里是记录的递增序列的开始位置和序列的长度

    代码:

    #include<stdio.h>
    int a[100005];
    int main(){
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
    	
    	//长度     长度最大值  序列开始的位置
        int len = 0, max = 0, left = 0;
    
        for(int i=0; i<n; i++){
            len = 0;
            for(int j=i+1; j<n; j++){
            //当后一个数大于前一个数,此序列的长度+1;
            //否则不满足递增的条件,退出循环,重新定义序列的开始位置
                if(a[j] > a[j-1]) len++;
                else break;
             }
            if(len > max){
                max = len;
                left = i;
            }
        }
        for(int i=left; i<=left+max; i++){
            if(i == left) printf("%d", a[i]);
            else printf(" %d", a[i]);
        }
        return 0;
    }
    
    展开全文
  • 最长连续递增子序列c语言

    千次阅读 2021-04-02 10:36:49
    最长连续递增子序列题目答案注意 题目 答案 #include<stdio.h> int main() { int n; scanf("%d",&n); int a[n],i; for(i=0;i<n;i++) scanf("%d",&a[i]); int count=0,max=0,flag=0,...

    最长连续递增子序列

    题目

    在这里插入图片描述

    答案

    #include<stdio.h>
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	int a[n],i;
    	for(i=0;i<n;i++)
    	scanf("%d",&a[i]);
    	
    	int count=0,max=0,flag=0,position=0;
    	for(i=0;i<n;i++)
    	{
    		if(count==0)
    		count++;
    		else if(count>0)
    		{
    			if(a[i]>a[i-1]) count++;
    			else 
    			{
    				if(count>max) 
    				{
    					position=i-count;
    					max=count;
    				}
    				count=0;
    				i--;
    			}
    		}
    		if(i==n-1) 
    		{
    			if(count>max) 
    				{
    					position=i-count+1;
    					max=count;
    				}
    		}
    	}	
    	printf("%d",a[position]);
    	for(i=position+1;i<position+max;i++)
    	printf(" %d",a[i]);
    } 
    

    注意

    遍历到数组的最后一个元素后,要做最后的处理;如果递增子序列的最后一个元素恰巧也是数组的最后一个元素,positioni-count的基础上还要加1

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

    给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

    输入格式:

    输入第1行给出正整数nn(≤105≤10​5​​);第2行给出nn个整数,其间以空格分隔。

    输出格式:

    在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序列结尾不能有多余空格。

    输入样例:

    15

    1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

    输出样例:

    3 4 6 8

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    const int maxn=1e5;

    int n;

    int a[maxn+5];

    int dp[maxn+5];

    int search(int num,int l,int r)

    {

    int mid;

    while(l<=r)

    {

    mid=(l+r)/2;

    if(num>dp[mid])

    l=mid+1;

    else

    r=mid-1;

    }

    return l;

    }

    int main()

    {

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

    scanf("%d",&a[i]);

    }

    memset(dp,0,sizeof(dp));

    dp[1]=1;

    for(int i=2;i<=n;i++)

    {

    if(a[i]>a[i-1])

    dp[i]=dp[i-1]+1;

    else

    dp[i]=1;

    }

    int max=0;

    int pos=0;

    for(int i=n;i>=1;i--)

    {

    if(max<=dp[i])

    {

    max=dp[i];

    pos=i;

    }

    }

    for(int i=pos-dp[pos]+1;i<=pos;i++)

    {

    if(i!=pos)

    printf("%d ",a[i]);

    else

    printf("%d\n",a[i]);

    }

    return 0;

    }

    展开全文
  • 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。input输入第1行给出正整数n(≤10​5​​);第2行给出n个整数,其间以...
  • 先说思路: 定义并初始化一个B[]数组,初始值为1,存储每个位置开始连续递增的长度; 然后找出B[]数组的最大值(子序列的最大长度)x及其下标y...在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序.
  • #include<stdio.h> int biger(int n1,int n2){ if(n1>n2){ return n1; } return n2; } int get_height(int arr[],int n){ if(n==1){ return 1; } int b[n]; for(int i=0;... int r.
  • leetcode-674. 最长连续递增序列-C语言

    千次阅读 2019-05-28 15:45:22
    int findLengthOfLCIS(int* nums, int numsSize){ int i; int max = 0; int tmp = 0; if(!nums || !numsSize) return 0; //printf("numsSize = %d \n", numsSize); ...
  • 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10 5 );第2行给出n个整数,其间...
  • 最长递增子序列

    2018-03-29 11:30:32
    最长递增子序列 51Nod - 1134 1.第一种方法(两层for循环暴力)#include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; ...
  • 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤10 5 );第2行给出n个整数,其间...
  • 最长连续递增子序列

    2021-10-03 10:28:19
    给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤105);第2行给出n个整数,其间...
  • 存储扩展算法n2编程c 写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中的最长递增子序列的长度。例如:在序列1,-1,2,-3,4,-5,6,-7中,其最长的递增子序列为1,2,4,6 或者 -1,2,4,6。(编程之美...
  • C语言 顺序表
  • 最长递增子序列之动态规划(C语言实现)

    千次阅读 多人点赞 2020-05-10 23:30:00
    (1)设置一个mark[]数组,mark[]数组的个数和原序列data[]的个数相等,mark[i]表示以data[i]作为结尾的最长递增子序列的长度; (2)在确定mark[i]时,在0到i-1中找到这样一个k,使得data[k]<data[i]且mark[k]=...
  • //计算最长递增子序列的长度,计算B数组的元素,array[]循环完一遍后,B的长度len即为所求 int BiSearch(int *b, int len, int w); //做了修改的二分搜索算法 int main() { printf("LIS: %d\n", LIS(array, ...
  • 这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
  • 所有题目源代码:Git地址 题目 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。...解释:最长递增子序列
  • 设计算法找出n个数组成的序列的最长单调递增子序列 问题:设计一个O(n^2)时间算法,找出由n个数组成的序列的最长单调递增子序列C语言实现如下: #include<stdio.h> #include<stdlib.h> void find_max...
  • Sample Input 5 2 5 3 1 4 Sample Output 5 13 0 8 0 思路:动态规划 +最长递增子序列思想 先将 数字序列每个长度的最长的递增子序列长度找到 例如 1 2 3 4 5 (下标) a[i] 2 5 3 1 4 dp[i] 1 2 2 1 3 dp[i]代表当前...
  • 假设存在一个序列d[1..9] = 2 1 5...此外,我们用一个变量Len来记录现在最长算到多少了 首先,把d[1]有序地放到B里,令B[1] = 2,就是说当只有1一个数字2的时候,长度为1的LIS的最小末尾是2。这时Len=1 然后,把d[2]...
  • 7-2 最长连续递增子序列 (20 分)

    千次阅读 2021-03-10 16:50:14
    7-2 最长连续递增子序列 (20 分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n(≤...
  • 300. 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] ...
  • #include &lt;iostream&gt; using namespace std; const int maxn = 100; int min_end[maxn]; //min_end[i]表示长度为i的子串的最小末端 ... //当前找到的长度为i的递增子序列的最小末尾的索引 in...
  • } 复杂度分析 时间复杂度: O(N)O(N)O(N), 空间复杂度: O(1)O(1)O(1), 方法二:dp 定义状态: dp[i] 表示区间 [0, i] 位置的最长连续上升子序列的长度。 状态转移方程: 如果 nums[i−1][i]nums[i-1] [i]nums[i...
  • 文章目录最长上升( 递增 )子序列与... 最长递增子序列的个数题目描述dp 解法 最长上升( 递增 )子序列与最长连续上升( 递增 )子序列( LIS ) 1. 最长上升子序列 LintCode题目地址: 76. 最长上升子序列 Leet...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,294
精华内容 917
关键字:

最长连续递增子序列c语言