其实这个题目和求最长递增子序列的题目是一个思想,就是用DP做
代码如下:
// Dp5.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int MAX=1000;
int dp[MAX];
int data[MAX];
//找到最长递增序列的长度
int solveIncre(int a[],int len)
{
int ans=0;
for(int i=0;i<len;i++)
{
for (int j=0;j<i;j++)
{
if (a[j]<a[i]&&dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
}
}
if (dp[i]>ans)
{
ans=dp[i];
cout<<a[i]<<" ";
}
}
cout<<endl;
return ans;
}
int solveDece(int a[],int len)
{
int ans = 0;
for (int i=0;i<len;i++)
{
for(int j=0;j<i;j++)
{
if (a[i]<a[j] && dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
}
}
if (ans<dp[i])
{
ans=dp[i];
cout<<a[i];
}
}
cout<<endl;
return ans;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cin>>n;
for (int i=0;i<n;i++)
{
cin>>data[i];
dp[i]=1;
}
//int ans = solveIncre(data,n);
int ans=solveDece(data,n);
cout<<ans<<endl;
system("pause");
return 0;
}
/////////////////////////////////////////////////
华丽的分割线
/////////////////////////////////////////////////
// Dp5.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int MAX=1000;
int dp[MAX];
int data[MAX];
//找到最长递增序列的长度
int solveIncre(int a[],int len)
{
int ans=0;
for(int i=0;i<len;i++)
{
for (int j=0;j<i;j++)
{
if (a[j]<a[i]&&dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
}
}
if (dp[i]>ans)
{
ans=dp[i];
cout<<a[i]<<" ";
}
}
cout<<endl;
return ans;
}
int solveDece(int a[],int len)
{
int ans = 0;
for (int i=0;i<len;i++)
{
for(int j=0;j<i;j++)
{
if (a[i]<a[j] && dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
}
}
if (ans<dp[i])
{
ans=dp[i];
cout<<a[i];
}
}
cout<<endl;
return ans;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cin>>n;
for (int i=0;i<n;i++)
{
cin>>data[i];
dp[i]=1;
}
//int ans = solveIncre(data,n);
int ans=solveDece(data,n);
cout<<ans<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
详细介绍最长递减子设有一个整数序列A1, A2, ... An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 ...
使用C++实现最短子序列,对正在学习算法的同学应该挺有帮助的
递减子序列.py
C++程序员面试、笔试经常遇到的一些算法示例集 pdf,相关内容:字符串匹配的KMP算法,括号匹配检测、求一个数组的最长递减字序列、一些数字题求解,输出一个字符串的所有组合,马戏团表演问题、Thread.sleep 与obj....
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元 素的情况下,该数组能否变成一个非递减数列。非递减数列定义如下:对 于数组中所有的 i (1 ),满足 array[i] [i + 1]
写了一个类,可以实现求连通图的最长路径 大家看看也可以帮忙找找有没有问题 很是担心算法想得有问题啊
里面主要有关于线性问题中最长公共子序列,最长递增递减子序列,最大子段和,需不需要输出位置,还有最长公共递增子序列,当然,最重要的是可以直接用
# 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 # 输入示例 # 输入:nums = [-4,-1,0,3,10] # 输出:[0,1,9,16,100] # 解释:平方后,数组变为 [16,...
输入两个数,查找位于位于这两数区间的序列
两个升序的数组A、B,将AB合并到C,保持升序,去除重生的元素
从键盘输入两个链表,通过程序对他们排序,之后按递增顺序合并链表
判断数据递增的方法,递归算法,简单明了 快速高效
力扣热题Python源代码 题目34. 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。... nums 是一个非递减数组 -109 <= target <= 109
可行的算法之一为:从表La与Lb中各取一个元素进行比较,将小的元素插入到Lc中,并取小元素所在表的下一个元素继续与另一表的元素继续比较操作,直到一个表中元素取尽为止,再将另一表的余下元素直接挂入新表Lc的末尾...
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路参考博客
有两个指数递减的一元多项式 先求这两个多项式的和 在求积 没问题的代码
对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例输出 1 2 9 22 43 56 堆排序 对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例输出 1 2 9 ...
题目把一个数组最开始的若干个元素搬到数组的末尾,称之为数组的旋转输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素NOTE:给出的所有元素都大于0,若数
子序列 返回int子序列的函数。 最长的递增子序列 最长的递减子序列 最长的公共子序列 公共区域。
判断字符串或者密码是不是连续递增的如1234567 7654321 abcdefg 之类的