DP基本都会讲到的一个问题LIS:longest increasing subsequence。
今晚上看了下动态规划, 求解了一下这个lis问题。
首先得看下在wiki上的对longest increasing subsquence的定义和解释:wiki
代码如下:
#include <iostream>
using namespace std;
int LIS(int A[], int len)
{
int *d = new int[len];
int longest_sub = 1;
d[0] = 1;
/*
for (int i = 1; i < len; i++)
{
d[i] = 1;
if (A[i-1] <= A[i])
{
d[i] = d[i-1] + 1;
}
if (d[i] > longest_sub)
{
longest_sub = d[i];
}
} */
for (int i = 0; i < len; i++)
{
d[i] = 1;
for (int j = 0; j < i; j++)
{
if (A[i-1] <= A[i] && d[j] + 1 > d[i])
{
d[i] = d[j] + 1;
}
}
if (d[i] > longest_sub)
{
longest_sub = d[i];
}
}
delete [] d;
return longest_sub;
}
int main()
{
int A[] = {5, 3, 4, 8, 6, 7};
int ls = LIS(A, 6);
cout << "********************************" << endl;
std::cout << ls << std::endl;
return 0;
}
如有错误,请指出,谢谢。
分享到:
相关推荐
adobe-fonts-revealer::fleur-de-lis:将Adobe Fonts(OTF)复制到您的下载目录
侦察兵 :fleur-de-lis: - 高级项目经理 瑞秋 侦察兵 :fleur-de-lis: -数字产品经理 斯特凡诺 侦察兵 :fleur-de-lis: -UX设计器 亚当 侦察兵 :fleur-de-lis: -数字志愿者 哈雷 侦察兵 :fleur-de-lis: -数字志愿者 ...
Vaadin Flow和Spring Boot的... 将项目作为Maven项目导入到您选择的IDE中。 使用mvn spring-boot:run运行应用程序 在浏览器中打开 有关使用Vaadin Flow和Spring的文档,请访问 有关Vaadin Flow的更多信息,请访问 。
FT-LIS 线性系统的容错迭代求解器 假设:预处理期间没有错误 共轭梯度(CG) --------------------------------- r(0) = b - Ax(0) rho(-1) = 1 p(0) = (0,...,0)^T ---------------------------------- ...
Niver_lis 丽斯诞辰(姐姐)
LIS3DH中文应用文档.zip
最长上升子序列(Longest Increasing Subsequence,简称LIS)是指在一个序列中找到一个最长的子序列,使得子序列中的元素是递增排列的。这个问题在计算机科学中很常见,有多种解决方法,其中动态规划是最常用的方法...
LIS3DH具有超低功耗工作模式,可实现高级节能,智能睡眠唤醒以及恢复睡眠功能。
在项目目录中,可以运行: npm start 在开发模式下运行应用程序。 打开在浏览器中查看。 如果进行编辑,页面将重新加载。 您还将在控制台中看到任何棉绒错误。 npm test 在交互式监视模式下启动测试运行程序。 ...
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
LIS接口:接收仪器的请求(query);在LIS系统中检索该条码的测试项目(item);将测试的item转化为仪器的通道号...这种通道号在不同的仪器中是不同定义的,所以LIS中一定会有一个相关仪器的通道与测试项目的对应表;
LIS2DH12TR,LIS3DH应用笔记,lis3dhrt,3axis
三轴加速传感器LIS2DH12中文数据手册+开发手册+数据转换方法。含前辈备注使用心得
本资源为ST公司官方LIS3DH 、LIS3DSH驱动及例子。资源解压后的driver文件夹可直接在你的工程中应用:The driver is platform independent, you need only to complete the two functions for write and read from ...
里面含有加速度传感器LIS3DH的中英文datasheet,讲解的非常详细,而且还有官方提供的测试代码,及其本人用STM32写的测试代码(可以检测出急加速和急减速)。
:fleur-de-lis: 下午助理聊天机器人机器人以私人助理的身份管理您的PM :fleur-de-lis: 帮助接收来自陌生人的消息是否令人讨厌? PM Assistant Chat Bot适合您。 该机器人将帮助您管理所有PM,并保持聊天列表清洁。在...
单片机驱动LIS3DH,很详细的源码文档。
陀螺仪LIS3DH驱动程序,没有工程,LIS3DH驱动程序,使用都可以根据例程来写,只要再写两条程序就行了,在驱动程序中的读与写程序。
迈瑞BS系列 LIS协议接口
(已作为选择最后操作的所有可能间隔中的所有可能削减的一部分发布) 你总是可以找到最长的回文子序列并使用它。 str.length - LPS.length也会给你同样的答案。 同样,您也可以使用最长公共子序列技术。 你需要在str...