最长递增子序列 详解 CPP

目录

  • 前言
  • 思路梳理
    • 题解最优思路
  • 我的思路
    • 思路一 考虑连续 对一半 ×
    • 思路二 基于思路一的优化 ×
    • 思路三 基于思路二的优化 √ 通过了但是效率太低
  • 我的代码

前言

今天继续做动态dp的第三题，最大子序和，昨天做最大连续子数组的和已经有一些写状态转移方程的经验了，今天自己想了一个思路一。

思路梳理

题解最优思路

写到这里我想惊叹一下数学语言的魅力，因为我虽然想清楚了但是却表达不清楚。一个数学公式代替了我的一大坨废话。
在这里插入图片描述

在这里插入图片描述
这里最大的坑在于，状态转移的前一个状态需要满足两个条件。从我自己的思路三优化到这里也并不复杂，感觉我自己的思路就好像是先把水煮开再一起下饺子，官方思路是冷水的时候我就可以把饺子放下去慢慢煮了。很多判断可以在遍历的时候就做了。
以下是代码：

int max_subArr_Ascending_order_optimize_Original(vector<int> Arr) {
    vector<int> resArr(Arr.size());
    for (int i = 0; i < Arr.size(); i++) {
        //先把最差的情况确定好，最差的情况也不过就是1了
        resArr[i] = 1;
        //然后再循环左边比它小的最大值
        for (int j = 0; j < i; j++) {
            if (Arr[j] < Arr[i]) {
                resArr[i] = max(resArr[j] + 1, resArr[i]);
            }
        }
    }
    return *max_element(resArr.begin(),resArr.end());
}

我的思路

思路一 考虑连续 对一半 ×

跟昨天的类似，也是以子数组的最后一个元素的位置作为标记。首先我找到最大的连续升数组，然后再在这个基础上加上前面的不连续的。但是很遗憾，这个思路只通过了一半的测试用例，想想看确实是有很大问题的。不应该考虑连续，连续的bug太大了。
在这里插入图片描述

class Solution {
public:
    int lengthOfLIS(vector<int>& Arr) {
        int res = 1;
        vector<int> resArr(Arr.size());
        resArr[0] = 1;
        int left_max_location;
        for (int i = 1; i < Arr.size(); i++) {
            // 首先找到左边比它小，且最大的元素
            left_max_location = search_left_less_than(i, Arr, resArr);
            if (left_max_location == -1) {
                resArr[i] = 1;
            } else {
                resArr[i] = left_max_location + 1;
            }
            if (resArr[i] >= res) {
                res = resArr[i];
            }
        }
        return res;
    }

    int search_left_less_than(int i, vector<int>& Arr, vector<int>& resArr) {
        // 如果这个元素比前面的所有元素都小的话，就返回-1
        if (*min_element(Arr.begin(), Arr.begin() + i) >= Arr[i]) {
            return -1;
        }
        // 重新设置一个数组，把所有值比i元素小的都存进去。
        vector<int> left_less(i);

        for (int j = i - 1; j >= 0; j--) {
            if (Arr[j] < Arr[i]) {
                left_less.push_back(resArr[j]);
            }
        }
        // 存好了之后我现在就找一个最大值了
        int left_location_max =
            *max_element(left_less.begin(), left_less.end());
        // 直接把这个最大值给返回出去
        return left_location_max;
    }
};

思路二 基于思路一的优化 ×

思路二我继续来考虑怎么去设置这个状态转移方程，以i位置结束的连续递增数组，它和次长的递增数组没有 物理空间 上 紧挨着的 特征了。因此我觉得它应该考虑的是 数组左边 第一个比它小的元素值，在它的基础上＋1。如此我们可以得到一下总结：

  1. 我们给最大子数组设置标签：子数组在i元素处结尾，设置一个resArr来存储以这个结尾的最大递增长度。
  2. 考虑初始条件：resArr[0]初始化为1；
  3. 状态转移方程：resArr[i]等于resArr[j]+1 ( j 为 i 的左边第一个小于自己本身元素的位置） 如果这个元素是从0到i最大的，就直接令resArr=1；

这个思路也是错的，并不是数组左边第一个值比它小的元素，而是需要满足①比它小 ②以这个位置结束的递增子数组的长度值要是最大的

思路三 基于思路二的优化 √ 通过了但是效率太低

修改了之后，发现我的解答还是错误，一行行debug发现是我的函数用的有问题：

vector函数自己有丰富的方法，可以直接帮我们找到数组里面的最大值，方法是max_element（要引入algorithm库），但是它其实有点类似于python的切片，函数的参数要给出vecotor的迭代器（Arr.begin(),Arr.end()）,我的错误就在于这个函数他的索引对象是从参数一开始到参数二的前一个，（Arr.end()其实就是指向vector最后一个参数的下一个）。

在这里插入图片描述
修改之后，测试都通过了，但是超出内存限制了。

这个其实是因为我在传递函数的时候没有使用引用，没使用引用就会在调用的时候复制一遍占用大量内存。

改完之后，终于通过了。。。但是依旧感觉好菜哈哈哈哈。
在这里插入图片描述

class Solution {
public:
    int lengthOfLIS(vector<int>& Arr) {
        int res = 1;
        vector<int> resArr(Arr.size());
        resArr[0] = 1;
        int locate = 0;
        int left_max_location;
        for (int i = 1; i < Arr.size(); i++) {
            //首先找到左边比它小，且最大的元素
            left_max_location = search_left_less_than(i, Arr, resArr);
            if (left_max_location == -1) {
                resArr[i] = 1;
            }
            else {
                resArr[i] = left_max_location + 1;
            }
            if (resArr[i] >= res) {
                res = resArr[i];
                locate = i;
            }
        }
        return res;
    }

        int search_left_less_than(int i, vector<int> &Arr, vector<int> &resArr) {
        //如果这个元素比前面的所有元素都小的话，就返回-1
        if (*min_element(Arr.begin(), Arr.begin() + i ) >= Arr[i]) {
            return -1;
        }
        vector<int> x = resArr;
        //重新设置一个数组，把所有值比i元素小的都存进去。
        vector<int> left_less(i, 0);
       
        for (int j = i - 1; j >= 0; j--) {
            if (Arr[j] < Arr[i]) {
                left_less[j] = resArr[j];
            }
        }
        //存好了之后我现在就找一个最大值了
        int left_location_max = *max_element(left_less.begin(), left_less.end());
        //直接把这个最大值给返回出去
        return left_location_max;
    }
};

我的代码

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

class solution {
public:
    //int max_subArr_sum(vector<int> Arr) {
    //    int res = Arr[0];
    //    vector<int> resArr(Arr.size());
    //    resArr[0] = res;
    //    for (int i = 1; i < Arr.size(); i++) {
    //        /*if (resArr[i - 1] + Arr[i] > resArr[i - 1]) {
    //            resArr[i] = resArr[i - 1] + Arr[i];
    //        }
    //        else {
    //            resArr[i] = resArr[i - 1];
    //        }
    //        if (resArr[i] > res) {
    //            res = resArr[i];
    //        }*/
    //        if (resArr[i - 1] > 0) {
    //            resArr[i] = resArr[i - 1] + Arr[i];
    //        }
    //        else {
    //            resArr[i] = Arr[i];

    //        }
    //        if (resArr[i] > res) {
    //            res = resArr[i];
    //        }
    //    }
    //    return res;
    //}

    //int max_subArr_Ascending_order(vector<int> Arr) {
    //    int res = 1;
    //    vector<int> resArr(Arr.size());
    //    resArr[0] = 1;
    //    int locate = 0;
    //    for (int i = 1; i < Arr.size(); i++) {
    //        if (Arr[i - 1] >= Arr[i]) {
    //            resArr[i] = 1;
    //        }
    //        else {
    //            resArr[i] = resArr[i - 1] + 1;
    //        }
    //        if (resArr[i] >= res) {
    //            res = resArr[i];
    //            locate = i;
    //        }
    //    }
    //    int current_max = Arr[locate - resArr[locate] + 1];
    //    for (int i = locate - 1; i >= 0; i--) {
    //        if (Arr[i] < current_max) {
    //            res++;
    //            current_max = Arr[i];
    //        }
    //    }
    //    return res;
    //}

    int max_subArr_Ascending_order_optimize(vector<int> Arr) {
        int res = 1;
        vector<int> resArr(Arr.size());
        resArr[0] = 1;
        int left_max_location;
        for (int i = 1; i < Arr.size(); i++) {
            //首先找到左边比它小，且最大的元素
            left_max_location = search_left_less_than(i, Arr, resArr);
            if (left_max_location == -1) {
                resArr[i] = 1;
            }
            else {
                resArr[i] = left_max_location + 1;
            }
            if (resArr[i] >= res) {
                res = resArr[i];
            }
        }       
        return res;
    }

    int search_left_less_than(int i, vector<int> &Arr, vector<int> &resArr) {
        //如果这个元素比前面的所有元素都小的话，就返回-1
        if (*min_element(Arr.begin(), Arr.begin() + i ) >= Arr[i]) {
            return -1;
        }
        //重新设置一个数组，把所有值比i元素小的都存进去。
        vector<int> left_less(i);
        
        for (int j = i - 1; j >= 0; j--) {
            if (Arr[j] < Arr[i]) {
                left_less.push_back(resArr[j]);
            }
        }
        //存好了之后我现在就找一个最大值了
        int left_location_max = *max_element(left_less.begin(), left_less.end());
        //直接把这个最大值给返回出去
        return left_location_max;
    }

    int max_subArr_Ascending_order_optimize_Original(vector<int> Arr) {
        vector<int> resArr(Arr.size());
        for (int i = 0; i < Arr.size(); i++) {
            //先把最差的情况确定好，最差的情况也不过就是1了
            resArr[i] = 1;
            
            //然后再循环左边比它小的最大值
            for (int j = 0; j < i; j++) {
                if (Arr[j] < Arr[i]) {
                    resArr[i] = max(resArr[j] + 1, resArr[i]);
                }
            }
        }
        return *max_element(resArr.begin(),resArr.end());
    }
};

int main() {
    solution s;
    vector<int> Arr = { 3,1,2 };
    int x = s.max_subArr_Ascending_order_optimize(Arr);
    cout << x << endl;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/609623.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Docker Compose：简化多容器应用部署

Docker Compose：简化多容器应用部署

序言 在当今的软件开发中&#xff0c;容器化技术的使用已经很普遍了。而 Docker 作为其中最流行的容器化平台之一&#xff0c;为开发者提供了方便、快捷、一致的开发和部署环境。但是&#xff0c;当我们的应用开始变得更加复杂&#xff0c;涉及到多个容器时&#xff0c;手动管…
阅读更多...
kafka（七）——消息偏移（消费者）

kafka（七）——消息偏移（消费者）

概念 消费者消费完消息后&#xff0c;向_consumer_offset主题发送消息&#xff0c;用来保存每个分区的偏移量。 流程说明 consumer发送JoinGroup请求&#xff1b;coordinator选出一个consumer作为leader&#xff0c;并将topics发送给leader消费者&#xff1b;leader consumer…
阅读更多...
4. Python的深拷贝、浅拷贝

4. Python的深拷贝、浅拷贝

文章目录 0、先说结论1、浅拷贝修改元素值2、深拷贝修改元素值学习链接 0、先说结论 无论深拷贝还是浅拷贝都会为新对象分配一块新的内存&#xff0c;因此新老对象id不相同。 对于浅拷贝&#xff0c;新老对象内部的可变and不可变元素id都是相同的(在没修改元素值之前)。 对于深…
阅读更多...
springboot -多数据源管理方案

springboot -多数据源管理方案

多数据源的配置有多种方式 方式一 、依赖dataSource的配置 1.建立多数据源配置 spring:# 数据源配置datasource:pdm:driver-class-name: oracle.jdbc.driver.OracleDriverjdbc-url: jdbc:oracle:thin:10.216.xxx.xxx:3000:orclusername: cfpdmpassword: capecapp:driver-cla…
阅读更多...
移动安全测试框架-MobSF window环境配置

移动安全测试框架-MobSF window环境配置

一. 介绍&#xff1a; MOBSF&#xff08;Mobile Security Framework&#xff09;是一个开源的移动安全渗透测试框架&#xff0c;用于评估移动应用程序的安全性。它提供了一组功能强大的工具和技术&#xff0c;帮助安全专业人员和开发人员发现和修复移动应用程序中的安全漏洞。 …
阅读更多...
React 第二十六章 Hook useCallback

React 第二十六章 Hook useCallback

useCallback 是 React 提供的一个 Hook 函数&#xff0c;用于优化性能。它的作用是返回一个记忆化的函数&#xff0c;当依赖发生变化时&#xff0c;才会重新创建并返回新的函数。 在 React 中&#xff0c;当一个组件重新渲染时&#xff0c;所有的函数都会被重新创建。这可能会…
阅读更多...
【npm】解决npm包突然消失MODULE_NOT_FOUND

【npm】解决npm包突然消失MODULE_NOT_FOUND

今天折腾新特性时需要升级nodejs&#xff0c;安装新版后npm离奇消失了。C:\Users\**用户名\AppData\Roaming\npm\node_modules下只有cnpm&#xff0c;没有npm的目录。重装nodejs也不好使。 机智如我&#xff0c;试了下cnpm -v是正常的&#xff0c;而且能看到nodejs&#xff0c;…
阅读更多...
CSP-j 2022csp-j完善程序易错题

CSP-j 2022csp-j完善程序易错题

易错题 答案23&#xff1a; 对 解析23&#xff1a; 函数 g 就是把函数 f 改成递推的形式 答案24&#xff1a; 对 解析23&#xff1a; 无。 答案25&#xff1a; C 解析25&#xff1a; m n ( m - 1 ) * ( 1 2 3 4 ... n ) O(mn^2) 答案26&#xff1a; C 解析26&#x…
阅读更多...
跨境电商行业蓬勃发展，武汉星起航引领卖家孵化新潮流

跨境电商行业蓬勃发展，武汉星起航引领卖家孵化新潮流

近年来&#xff0c;我国跨境电商行业在政府的大力扶持下呈现出强劲的发展势头。随着国内制造业结构的加速调整与居民消费需求升级态势的持续凸显&#xff0c;跨境出口规模占比稳步提升&#xff0c;跨境进口规模同样不断扩大&#xff0c;行业市场规模持续增长。在这一背景下&…
阅读更多...
vue3+ant design实现表格数据导出Excel

vue3+ant design实现表格数据导出Excel

提示：实现表格数据导出Excel 文章目录 前言 一、安装ant design？ 二、引用ant design 1.搭建框架 2.获取表格数据 三、封装导出表格的代码 四、导出 1.获取导出地址 2.在下载导出事件中添加导出代码 五、全部代码 前言 今天终于有时间来更新文章了，最近公司项目比较紧…
阅读更多...
【ArcGIS Pro微课1000例】0058：玩转NetCDF多维数据集

【ArcGIS Pro微课1000例】0058：玩转NetCDF多维数据集

一、NetCDF介绍 NetCDF(network Common Data Form)网络通用数据格式是由美国大学大气研究协会（University Corporation for Atmospheric Research，UCAR）的Unidata项目科学家针对科学数据的特点开发的，是一种面向数组型并适于网络共享的数据的描述和编码标准。NetCDF广泛应…
阅读更多...
pgsql查看指定模式的存储过程

pgsql查看指定模式的存储过程

pgsql查看指定模式的存储过程 在 PostgreSQL 中&#xff0c;如果你想要查看指定模式的存储过程&#xff08;也称为函数&#xff09;&#xff0c;你可以使用 \df 或 \df 命令在 psql 命令行工具中&#xff0c;或者使用 SQL 查询来从 pg_catalog 系统模式中查询。 \df命令行查询…
阅读更多...
吴恩达2022机器学习专项课程C2（高级学习算法）W1（神经网络）：Lab01 神经元和层

吴恩达2022机器学习专项课程C2（高级学习算法）W1（神经网络）：Lab01 神经元和层

目录 导入Tensorflow的库无激活函数 vs 有激活函数&#xff1f;1.无激活函数2.有激活函数 无激活函数的神经元-回归/线性模型1.创建训练集散点图2.创建层3.层输入4.获取层参数5.层参数的形状6.手动设置层的参数7.层计算vs线性回归模型计算 有激活函数sigmoid的神经元1.创建训练…
阅读更多...
武汉星起航深耕亚马逊跨境电商，引领中国卖家开拓全球市场新篇章

武汉星起航深耕亚马逊跨境电商，引领中国卖家开拓全球市场新篇章

在全球经济深度融合的当下&#xff0c;跨境电商已成为连接中国与世界市场的重要桥梁。作为跨境电商领域的佼佼者&#xff0c;武汉星起航电子商务有限公司凭借对亚马逊平台的深入了解和丰富经验&#xff0c;成功引领了中国卖家开拓全球市场的新篇章。 亚马逊&#xff0c;这家起…
阅读更多...
计算机发展史故事【7】

计算机发展史故事【7】

二战建奇勋 布雷契莱庄园当然不信德寇的邪说&#xff0c;他们把大约200 名精干人员集中在“3号棚”&#xff0c;四班轮换&#xff0c;24 小时值守&#xff0c;专门对付德国的“斯芬克司之谜”。图林则带着副手、象棋冠军亚历山大&#xff0c;领导着“8 号棚”&#xff0c;进行…
阅读更多...
安卓开发--新建工程，新建虚拟手机，按键事件响应

安卓开发--新建工程，新建虚拟手机，按键事件响应

安卓开发--新建工程&#xff0c;新建虚拟手机&#xff0c;按键事件响应 1.前言2.运行一个工程2.1布局一个Button2.2 button一般点击事件2.2 button属性点击事件2.2 button推荐点击事件 本篇博客介绍安卓开发的入门工程&#xff0c;通过使用按钮Buton来了解一个工程的运作机制。…
阅读更多...
【论文合集1】- 存内计算加速机器学习

【论文合集1】- 存内计算加速机器学习

本章节论文合集&#xff0c;存内计算已经成为继冯.诺伊曼传统架构后&#xff0c;对机器学习推理加速的有效解决方案&#xff0c;四篇论文从存内计算用于机器学习&#xff0c;模拟存内计算&#xff0c;对CNN/Transformer架构加速角度阐述存内计算。 【1】WWW: What, When, Where…
阅读更多...
Web实时通信的学习之旅：WebSocket入门指南及示例演示

Web实时通信的学习之旅：WebSocket入门指南及示例演示

文章目录 WebSocket的特点1、工作原理2、特点3、WebSocket 协议介绍4、安全性 WebSocket的使用一、服务端1、创建实例&#xff1a;创建一个webScoket实例对象1.1、WebSocket.Server(options[&#xff0c;callback])方法中options对象所支持的参数1.2、同样也有一个加密的 wss:/…
阅读更多...
2024第九届数维杯数学建模论文模板（内附LaTeX+Word）

2024第九届数维杯数学建模论文模板（内附LaTeX+Word）

一年一度的2024年第九届数维杯国赛报名进行中&#xff01;相信很多同学们已经摩拳擦掌蓄势待发了&#xff01; 经历三天比赛&#xff0c;最后提交的论文就是最终答卷&#xff0c;那么一篇数模论文&#xff0c;包括哪些内容呢&#xff1f; 一篇完整的数模论文&#xff0c;包括…
阅读更多...
【初阶数据结构】单链表经典OJ题

【初阶数据结构】单链表经典OJ题

目录标题 原题展现题目解析代码展现1.创建新节点2.拷贝random指针3.将新节点尾插 原题展现 该题是力扣上的第138题&#xff0c;题目链接如下&#xff1a;随机链表的复制。 题目解析 我们发现这个链表和一般的链表存在着一点点区别&#xff0c;那就是每个节点多了一个random指…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站