【算法】动态规划最长上升子序列

ゝ一纸荒年。 2022-08-26 03:43 228阅读 0赞

/* *
     * 找出最长上升子序列的个数
     * 并输出一个最长子序列
     * */
    #include <stdio.h>
    #define MAX_STR_SIZE 50
    
    int main()
    {
    	int i = 0;
    	int j = 0;
    	int Max = 0;
    	int Maxlocate = 0;
    	char str[MAX_STR_SIZE];
    	int lque[MAX_STR_SIZE] = {0,};
    	scanf("%s",str);
    
    	while (str[i] != '\0')
    	{
    		lque[i] = 1;
    
    		for (j = 0; j <= i; j++)
    		{
    			if (str[i] > str[j])
    			{
    				lque[i] = lque[i] > lque[j]+1 ? lque[i] : lque[j]+1;
    
    				if (Max < lque[i])
    				{
    					Max = lque[i];
    					Maxlocate = i;
    				}
    			}
    		}
    
    		i++;
    	}
    
    	printf("\nThe Longest sequeue length is :%d\n",Max);
    
    	Max--;
    	char tmp = str[Maxlocate];
    	printf("%c ",tmp);
    
    	/* 输出时  从最大值开始 逆序输出 */
    	while (--Maxlocate >= 0)
    	{
    		if (Max >= 1 && Max == lque[Maxlocate] && tmp > str[Maxlocate])
    		{
    			Max--;
    			tmp = str[Maxlocate];
    			printf("%c ",tmp);
    		}
    	}
    	printf("\n");
    
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode动态规划子序列问题——300.最长上升子序列

题目描述： [300. 最长递增子序列![icon-default.png?t=M4AD][icon-default.png_t_M4AD]https://leetcod

ゝ一世哀愁。/ 2023年10月03日 19:13/ 0 赞/ 41 阅读

相关 leetcode 最长上升子序列动态规划

> 给定一个无序的整数数组，找到其中最长上升子序列的长度。 > 示例: > 输入: \[10,9,2,5,3,7,101,18\] > 输出: 4 > 解释: 最长

梦里梦外;/ 2023年08月17日 15:43/ 0 赞/ 130 阅读

相关 lintcode76. 最长上升子序列动态规划

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。样例样例 1: 输入: [5,4,1,2,3] 输出: 3

灰太狼/ 2023年07月03日 08:17/ 0 赞/ 35 阅读

相关动态规划---最长上升子序列（不连续）

比如序列（1，7，3，5，9，4，8），它的最长上升序列是（1，3，4，8），所以它的最长上升序列长度为 4，那么给定任意长度的序列，请求出它的最长上升序列长度代码：

刺骨的言语ヽ痛彻心扉/ 2023年06月24日 11:26/ 0 赞/ 33 阅读

相关 673 最长递增子序列的个数（动态规划-最长上升子序列）

1. 问题描述：给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1: 输入: \[1,3,5,4,7\] 输出: 2 解释: 有两个最长递增子序列，

雨点打透心脏的1/2处/ 2022年09月02日 12:51/ 0 赞/ 211 阅读

相关【算法】动态规划最长上升子序列

/ 找出最长上升子序列的个数并输出一个最长子序列 / include <stdio.h> define MAX_

ゝ一纸荒年。/ 2022年08月26日 03:43/ 0 赞/ 229 阅读

相关最长上升子序列——动态规划

Think: 1递推思想反向推演递推关系1： b\[i\] = 1//i == 1 || Vi, max(b\[i\], b\[j+1\]) = 0; b\[

港控/mmm°/ 2022年06月17日 03:48/ 0 赞/ 244 阅读

相关 HDU 1160(动态规划-最长上升子序列)

问题描述： FatMouse believes that the fatter a mouse is, the faster it runs. To disprove thi

谁借莪１个温暖的怀抱￠/ 2022年06月03日 07:07/ 0 赞/ 222 阅读

相关动态规划：最长上升子序列

1.1 朴素方法 O（n ^2）: 思路：每个数都遍历他前面的所有数，如果这个数比前面的数要大，更新他自己或者他前面的数+1的最大的一个数。 include<ios

╰半橙微兮°/ 2022年01月22日 09:23/ 0 赞/ 270 阅读

相关动态规划-最长上升子序列LIS

文章目录问题描述一.简单推论（非0 n情况） 1.问题分析 2.状态转移方程 3.参考代码 4

￡神魔★判官ぃ/ 2021年09月07日 06:03/ 0 赞/ 444 阅读