跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客工具镜像开源精选AI社区
我的书AI 学习话题UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C++算法

C++ 算法实战:排序子序列划分与 LIS 优化

针对 C++ 笔试中的三类典型问题,分别探讨了贪心划分、数值消减与最长上升子序列的优化解法。第一题通过扫描数组识别非增或非减区间;第二题利用贪心策略最大化单次减法幅度;第三题使用二分查找优化 DP 状态转移,将复杂度降至 O(n log n)。代码已整理规范,可直接参考练习。

云间运维发布于 2026/3/28更新于 2026/11/1688 浏览
C++ 算法实战:排序子序列划分与 LIS 优化

一、排序子序列划分

题目解析

给定一个数组,判断这个子序列可以划分成多少个排序子序列。这里的排序子序列指的是连续的非递增或非递减子序列。

例如:1 2 3 2 2 1 可以划分成 1 2 3 和 2 2 1 两个排序子序列。

解题思路

这道题的核心在于贪心策略。我们只需要从左到右遍历数组,尽可能延长当前找到的排序子序列。

关键点:

  • 方向判定:遇到数值相等的区域时,这段相等序列既可以接在前面的非递增序列后,也可以接在非递减序列后。因此,遇到相等元素时,直接跳过继续向后看,直到发现大小变化再确定方向。
  • 边界处理:如果数组开头就是相等序列,直接跳过即可;如果最后一个元素无法与前一个序列合并,则单独作为一个新的子序列。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int arr[N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    int ret = 0;
    for (int i = 0; i < n; i++) {
        if (i == n - 1) { // 数组最后一个位置
            ret++;
            break;
        }
        if (arr[i] < arr[i + 1]) { // 非递减
            while (i < n && arr[i] <= arr[i + 1]) i++;
            ret++;
        } else if (arr[i] > arr[i + 1]) { // 非递增
            while (i < n && arr[i] >= arr[i + ]) i++;
            ret++;
        }  { 
             (i < n && arr[i] == arr[i + ]) i++;
        }
    }
    cout << ret << endl;
     ;
}
1
else
// 数组开始位置的相等子序列
while
1
return
0

二、消减整数

题目解析

给定一个正整数 H,从 1 开始减。第一次减去 1,之后每一次减去的数要么和上一次相等,要么是上一次的两倍。求最少需要几次才能将 h 减到 0。

解题思路

这是一个典型的贪心问题。我们的目标是让次数最少,所以每次减法应该尽可能大。

逻辑推导:

  • 设当前步长为 x(初始为 1),剩余值为 n。
  • 如果 n 是 2*x 的倍数,说明我们可以安全地减去 2*x 而不导致后续无法整除归零(或者说为了减少次数,优先选大的)。
  • 如果 n 不是 2*x 的倍数,但可能是 x 的倍数,那就只能减去 x。
  • 注意:题目要求第一次减去 1,所以初始 n 可以先减 1,步长 x 设为 1,计数 ret 设为 1。

代码实现

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        n--; // 第一次减去 1
        int ret = 1, x = 1;
        while (n) {
            if (n % (2 * x) == 0) x *= 2;
            n -= x;
            ret++;
        }
        cout << ret << endl;
    }
    return 0;
}

三、最长上升子序列 (二)

题目解析

给定一个数组,找到这个数组中最长严格上升子序列的长度。要求时间复杂度为 O(n log n)。

解题思路

暴力 DP 是 O(n^2),无法满足要求。我们需要维护一个辅助数组 dp,其中 dp[i] 表示长度为 i+1 的上升子序列中,末尾元素的最小值。

核心优化:

  1. 单调性:dp 数组本身是严格递增的。因为如果长度为 k 的子序列末尾最小值是 v,那么长度为 k+1 的子序列末尾一定大于 v。
  2. 二分查找:当遍历到新元素 e 时,如果 e 大于 dp 中所有元素,直接追加到末尾,长度加一。否则,在 dp 中找到第一个大于等于 e 的位置,将其替换为 e。这样做的目的是让该长度的子序列末尾更小,有利于后续扩展。

代码实现

#include <vector>
using namespace std;

class Solution {
public:
    int dp[100001];
    int pos = 0;

    int LIS(vector<int>& a) {
        for (auto& e : a) {
            if (pos == 0 || e >= dp[pos]) {
                dp[++pos] = e;
            } else {
                int l = 1, r = pos;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (dp[mid] >= e) r = mid;
                    else l = mid + 1;
                }
                dp[l] = e;
            }
        }
        return pos;
    }
};

以上三道题涵盖了常见的贪心与动态规划优化技巧,建议结合具体数据范围多动手调试。

目录

  1. 一、排序子序列划分
  2. 题目解析
  3. 解题思路
  4. 二、消减整数
  5. 题目解析
  6. 解题思路
  7. 三、最长上升子序列 (二)
  8. 题目解析
  9. 解题思路

更多推荐文章

查看全部
  • Python 与 NumPy、Pandas、Matplotlib 版本对应关系表
  • OpenAI Whisper 语音识别指南:环境搭建与批量转录实践
  • 滑动窗口算法详解:从入门到实战
  • PyCharm 集成 GitHub Copilot 安装与配置实战
  • 托马斯·哈代诗歌《散步》英文原诗及中译
  • OpenClaw Linux 安装与基础配置指南
  • C# 业务异常处理:BusException 类设计与使用
  • Python 编程语言现状与核心应用领域解析
  • Kubernetes 边缘 AI 部署与管理最佳实践
  • Android Kotlin 开发内嵌 WebView 应用及按键交互实践
  • MySQL CRUD 核心实战:增删改查语法与避坑指南
  • 解决新机型 Copilot 键替代右 Ctrl 键问题
  • ROS 2 机器人物理属性配置与 Gazebo 仿真导入实战
  • AI 辅助修复前端动态导入失败问题的实践与反思
  • QClaw 上手指南:本地 AI 代理框架深度体验
  • 使用 Claude Code 与 GLM4.7 调试前端 Bug 的实战复盘与反思
  • OpenClaw 部署实战:模型接入与飞书机器人配置
  • Python 数据科学工具链入门:NumPy、Pandas、Matplotlib 实战
  • 李飞飞:武断 AI 政策损害开源社区;纽约大学教授称或被 Altman 误导
  • Cameralink 图像输出和采集时序,针对FPGA开发

相关免费在线工具

  • 加密/解密文本

    使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online

  • Markdown转HTML

    将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online