您现在的位置是:首页 > 正文

算法导论—最长递增子序列

2024-04-01 01:16:01阅读 4

华电北风吹
日期:2016/2/20

问题描述:
例如数组arr=[1,5,8,2,3,4]的最长递增子序列是1,2,3,4

动态规划求解。对于数组中的每个元素,从前往后计算每个元素的状态——到这个元素为止所构成的最长递增子序列。时间复杂度 Θ(n2)
参考代码:

#include <iostream>
#include <fstream>
using namespace std;

#define MAXLENGTH 10

int LongestIncreasingSubsequence(int arr[], int n, int state[], int line[])
{
    int path[MAXLENGTH];
    for (int i = 0; i < n; ++i)
    {
        path[i] = i;
    }
    state[0] = 1;
    for (int i = 1; i < n; ++i)
    {
        state[i] = 1;
        for (int j = 0; j < i; ++j)
        {
            if (arr[i] >= arr[j] && state[j] + 1 > state[i])
            {
                state[i] = state[j] + 1;
                path[i] = j;
            }
        }
    }
    int max = 0;
    int end = -1;
    for (int i = 0; i < n; ++i)
    {
        if (state[i] > max)
        {
            max = state[i];
            end = i;
        }
    }
    int i = 1;
    line[0] = arr[end];
    while (path[end] != end)
    {
        line[i++] = arr[path[end]];
        end = path[end];
    }
    return max;
}
int main()
{
    ifstream in(".\\input.txt");
    cin.rdbuf(in.rdbuf());

    int n;
    int X[MAXLENGTH];
    int c[MAXLENGTH];
    int line[MAXLENGTH];
    while (cin >> n, n != 0)
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> X[i];
        }
        int max = LongestIncreasingSubsequence(X, n, c, line);
        cout << "Longest Increasing Subsequence's Length: " << max << endl;
        for (int i = max - 1; i >= 0; --i)
        {
            cout << line[i]<<" ";
        }
        cout << endl;
    }
}

网上见了一个比较巧妙的算法,代码如下(这里让我想到了快排的那种与这个特别像的实现方式)。目前下面的算法复杂度仍旧是 Θ(n2) ,但是对于内层循环的查找进行二分优化,可以使得复杂度降低为 Θ(nlogn)

#include <stdio.h>
#include<string.h>
char str[10001];
int main()
{
    int T, i, j;
    int len, ans;
    scanf("%d", &T);
    while (T--)
    {
        memset(str, 0, sizeof(str));
        scanf("%s%*c", str);
        len = strlen(str);
        ans = 0;
        for (i = 0; i < len; i++)
        {
            for (j = 0; j < ans; j++)
            {
                if (str[j] >= str[i])
                {
                    str[j] = str[i];
                    break;
                }
            }
            if (j == ans)
            {
                str[j] = str[i];
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

网站文章

  • 31省市数字经济“十四五”规划路线图

    31省市数字经济“十四五”规划路线图

    发展数字经济是把握新一轮科技革命和产业变革新机遇的战略选择。全文共计17783字,预计阅读时间12分钟来源| 数据观综合(转载请注明来源)编辑| 蒲蒲近年来,我国数字经济发展势头强劲,数字经济顶层设计持续完善,数字经济成为我国经济增长的重要推动力量。与此同时,各地纷纷出台相关政策措施,抢抓数字经济发展机遇。结合各地“十四五”规划及数字经济相关文件,数据观整理了31个...

    2024-04-01 01:15:36
  • Qt5 学习之路及嵌入式开发教程20:Qt5绘图---QPainter

    Qt5 学习之路及嵌入式开发教程20:Qt5绘图---QPainter

    Qt5 学习之路及嵌入式开发教程20:Qt5绘图---QPainter这次任务要完成Qt5 QPainter 2D-绘图界面设计及功能实现一、项目文件的建立1、新建文件或项目2、选择后,输入名称和路径,下一步:3、输入类名:这边输入Draw,选择基类:QWidget,下一步:4、下一步,直到点击中“完成”,完成文件设置。二、基本绘图1、重...

    2024-04-01 01:15:30
  • 推荐一款免费的带有坐标系的在线绘图web应用(汇报神器)

    推荐一款免费的带有坐标系的在线绘图web应用(汇报神器)

    这简直就是汇报党的福音,有时候汇报的时候,想描述一个变化过程往往需要坐标系加以支持,但是工业软件又过于难看,且复杂。那有没有可以简单快速的绘制带有坐标系的示意图工具呢?我搜了一下还真有。

    2024-04-01 01:15:21
  • 如何在Raspberry Pi上使用FreeBSD jails

    如何在Raspberry Pi上使用FreeBSD jails

    Container由于Linux上的Docker而变得广泛流行,但是有很多早期的实现,包括FreeBSD上的jail系统。 这个系统最早是在2000年以FreeBSD 4.0发行的,此后一直在不断改进...

    2024-04-01 01:14:56
  • shiro-基本原理和逻辑配置

    shiro-基本原理和逻辑配置

    https://jinnianshilongnian.iteye.com/blog/2049092 https://my.oschina.net/huangyong/blog/215153 http://shiro.apache.org/articles.html http://shiro.apache.org/documentation.html

    2024-04-01 01:14:49
  • 数据结构与算法-12爬楼梯

    Description 爬楼梯的时候,设每次可以上一级台阶或者两级台阶,计算上 n 级台阶的方案数。 Input 输入包含多组测试数据,对于每组测试数据: 输入只有一行为一个正整数 n(1 ≤ n ≤...

    2024-04-01 01:14:41
  • 服务器系统怎么设置第一启动项,服务器怎么设置启动项

    服务器系统怎么设置第一启动项,服务器怎么设置启动项

    服务器怎么设置启动项 内容精选换一换华为云帮助中心,为用户提供产品简介、价格说明、购买指南、用户指南、API参考、最佳实践、常见问题、视频帮助等技术文档,帮助您快速上手使用华为云服务。您需要在源端服务...

    2024-04-01 01:14:14
  • 用python批量修改文本文件编码格式

    用python批量修改文本文件编码格式,比如gb2312转为utf8,可以自定义格式

    2024-04-01 01:14:08
  • 设计模式概述

    设计模式概述

    设计模式(Design Pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结,使用设计模式是为了可重用代码、让代码更容易被他人理解并且保证代码可靠性。它代表了软件设计最佳的实践,是软件开发人员在软件开发过程中面临的一般问题的解决方案。

    2024-04-01 01:14:00
  • C++模板-35-类模板对象做函数参数的三种情况

    C++模板-35-类模板对象做函数参数的三种情况

    接着来学习类模板作为函数参数传入是如何使用,如果需要把类模板作为参数一起传入到函数中,一般有三种情况,下面分别用代码来解释这三种情况。 1.指定传入类型 就是在参数中,就指定类型,而不是, 而是直接指定确定类型,例如。看下面代码,在printPerson1()就是参数指定特定类型 #include #include using namespa.

    2024-04-01 01:13:53