[算法]-Longest Increasing Subsequence

简介:

看微软笔试题遇到的。

Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2,1,4,2,3,7,4,6} is {1,2,3,4,6}, and its LIS length is 5.Considering an array with N elements , what is the lowest time and space complexity to get the length of LIS?

算法一:动态规划

#include <iostream>
#include <vector>
using namespace std;
#define SIZE 8 
int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequence
int length[SIZE];  // 第 x 格的值為 s[0...x] 的 LIS 長度

void LIS()
{
    // 初始化。每一個數字本身就是長度為一的 LIS。
    for (int i=0; i<SIZE; i++) length[i] = 1;

    for (int i=0; i<SIZE; i++)
        // 找出 s[i] 後面能接上哪些數字,
        // 若是可以接,長度就增加。
        for (int j=i+1; j<SIZE; j++)
            if (s[i] < s[j])
                length[j] = max(length[j], length[i] + 1);

    // length[] 之中最大的值即為 LIS 的長度。
    int n = 0;
    for (int i=0; i<SIZE; i++)
        n = max(n, length[i]);
    cout << "LIS的長度是" << n;
}

int main(void)  
{  
    LIS();
    system("pause");  
    return 0;  
}
算法二:
#include <iostream>
#include <vector>
using namespace std;
#define SIZE 8 
int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequence
int b[SIZE];

// num为要查找的数,k是范围上限
// 二分查找大于num的最小值,并返回其位置
int bSearch(int num, int k)  
{  
    int low=1, high=k;  
    while(low<=high)  
    {  
        int mid=(low+high)/2;  
        if(num>=b[mid])  
            low=mid+1;  
        else   
            high=mid-1;  
    }  
    return low;  
}; 

void LIS()
{
    int low = 1, high = SIZE;
    int k = 1;
    b[1] = s[1];
    for(int i=2; i<=SIZE; ++i)
    {
        if(s[i]>=b[k])
            b[++k] = s[i];
        else
        {
            int pos = bSearch(s[i], k);
            b[pos] = s[i];
        }
    }
    printf("%d", k); 
}

int main(void)  
{  
    LIS();
    system("pause");  
    return 0;  
}




目录
相关文章
|
7月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
140 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
算法 Java 程序员
【手绘算法】力扣 3 无重复的最长字符串(Longest Substring Without Repeating Characters)
Hi,大家好,我是Tom。一个美术生转到Java开发的程序员。今天给大家分享的是力扣题第3题,无重复的最长字符串。在解题过程中,也会手写一些伪代码。当然,如果想要完整的源码的话,可以到我的个人主页简介中获取。 这道题呢属于中等难度,评估为四颗星,它的通过率只有39%。
142 0
|
算法 C#
算法题丨Longest Consecutive Sequence
描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
1142 0
|
12天前
|
算法 数据安全/隐私保护
基于GA遗传算法的悬索桥静载试验车辆最优布载matlab仿真
本程序基于遗传算法(GA)实现悬索桥静载试验车辆最优布载的MATLAB仿真(2022A版)。目标是自动化确定车辆位置,使加载效率ηq满足0.95≤ηq≤1.05且尽量接近1,同时减少车辆数量与布载时间。核心原理通过优化模型平衡最小车辆使用与ηq接近1的目标,并考虑桥梁载荷、车辆间距等约束条件。测试结果展示布载方案的有效性,适用于悬索桥承载能力评估及性能检测场景。
|
12天前
|
算法 机器人 数据安全/隐私保护
基于双向RRT算法的三维空间最优路线规划matlab仿真
本程序基于双向RRT算法实现三维空间最优路径规划,适用于机器人在复杂环境中的路径寻找问题。通过MATLAB 2022A测试运行,结果展示完整且无水印。算法从起点和终点同时构建两棵随机树,利用随机采样、最近节点查找、扩展等步骤,使两棵树相遇以形成路径,显著提高搜索效率。相比单向RRT,双向RRT在高维或障碍物密集场景中表现更优,为机器人技术提供了有效解决方案。
|
1月前
|
存储 算法 调度
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
|
12天前
|
算法 JavaScript 数据安全/隐私保护
基于GA遗传优化的最优阈值计算认知异构网络(CHN)能量检测算法matlab仿真
本内容介绍了一种基于GA遗传优化的阈值计算方法在认知异构网络(CHN)中的应用。通过Matlab2022a实现算法,完整代码含中文注释与操作视频。能量检测算法用于感知主用户信号,其性能依赖检测阈值。传统固定阈值方法易受噪声影响,而GA算法通过模拟生物进化,在复杂环境中自动优化阈值,提高频谱感知准确性,增强CHN的通信效率与资源利用率。预览效果无水印,核心程序部分展示,适合研究频谱感知与优化算法的学者参考。
|
1月前
|
算法 安全 数据安全/隐私保护
基于AES的遥感图像加密算法matlab仿真
本程序基于MATLAB 2022a实现,采用AES算法对遥感图像进行加密与解密。主要步骤包括:将彩色图像灰度化并重置大小为256×256像素,通过AES的字节替换、行移位、列混合及轮密钥加等操作完成加密,随后进行解密并验证图像质量(如PSNR值)。实验结果展示了原图、加密图和解密图,分析了图像直方图、相关性及熵的变化,确保加密安全性与解密后图像质量。该方法适用于保护遥感图像中的敏感信息,在军事、环境监测等领域具有重要应用价值。
|
2月前
|
算法 数据可视化 BI
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
本程序基于免疫算法实现物流仓储点选址优化,并通过MATLAB 2022A仿真展示结果。核心代码包括收敛曲线绘制、最优派送路线规划及可视化。算法模拟生物免疫系统,通过多样性生成、亲和力评价、选择、克隆、变异和抑制机制,高效搜索最优解。解决了物流仓储点选址这一复杂多目标优化问题,显著提升物流效率与服务质量。附完整无水印运行结果图示。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化TCN-GRU时间卷积神经网络时间序列预测算法matlab仿真
本项目基于MATLAB2022a开发,提供无水印算法运行效果预览及核心程序(含详细中文注释与操作视频)。通过结合时间卷积神经网络(TCN)和遗传算法(GA),实现复杂非线性时间序列的高精度预测。TCN利用因果卷积层与残差连接提取时间特征,GA优化超参数(如卷积核大小、层数等),显著提升模型性能。项目涵盖理论概述、程序代码及完整实现流程,适用于金融、气象、工业等领域的时间序列预测任务。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等