[算法]-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;  
}
AI 代码解读
算法二:
#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;  
}
AI 代码解读




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

你好,我是AI助理

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