程序员脑瘫，要不要写在简历上。。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一程序员因为脑瘫，肢体动作略显僵硬，问要不要写在简历上。有的网友建议写上，有的建议不要写，其实这种如果不影响工作的话可写也可不写。

不过我觉得最好写上，并且注明一下不会影响到工作。因为不写的话，面试的时候如果公司嫌弃，它会以各种理由拒绝，面试白跑一趟，也挺难受的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第300题：最长递增子序列。

问题描述

来源：LeetCode第300题

难度：中等

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2：

输入：nums = [7,7,7,7,7,7,7] 输出：1

• 1 <= nums.length <= 2500

• -10^4 <= nums[i] <= 10^4

问题分析

这题我们昨天刚讲过 ，使用的是动态规划的解决方式，这里我们使用二分查找的方式再来解这题。

我们把计算的最长递增子序列保存到集合list中，如果当前元素大于集合的最后一个元素，说明当前元素可以和集合构成一个更长的递增子序列，我们就把当前元素添加到集合中。

比如集合中的元素：[1,3,4,6]，当前元素是 8 ，如果把 8 添加到集合中就会构成更长的集合[1,3,4,6,8]。

如果当前元素小于集合的最后一个元素，为了保证 集合中的元素尽可能小 ，我们可以让当前元素替换集合中第一个大于它的元素。

比如集合中的元素：[1,3,5,6]，当前元素是 4 ，我们可以让 4 替换 5 ，变成[1,3,4,6]，因为 集合中的元素越小，构成最长递增子序列的机会就越大 。

因为集合中的元素都是有序的，所以替换只需要进行二分查找即可。

JAVA：

public int lengthOfLIS(int[] nums) {
    // mList中保存的是构成的上升子序列
    List
       
  mList =  new ArrayList<>(nums.length);      for ( int num : nums) {          // 添加到集合的最后          if (mList.size() ==  0 || mList.get(mList.size() -  1) < num)             mList.add(num);          else {              // 二分查找              int i = Collections.binarySearch(mList, num);              // 替换，这里要注意，如果查找到，i 会返回查找元素的下标，如果没              // 找到，就会返回它应该存放的位置，然后取反，所以是个负数。             mList.set((i <  0) ? -i -  1 : i, num);         }     }      return mList.size(); }

C++：

public:
    int lengthOfLIS(vector

  &nums) {         vector

  mList;         mList.reserve(nums.size());         for (int num: nums) {             if (mList.empty() || mList.back() < num) {                 mList.push_back(num);             } else {                 // 二分查找                 auto it = lower_bound(mList.begin(), mList.end(), num);                 *it = num;             }         }         return mList.size();     }

Python：

def lengthOfLIS(self, nums: List[int]) -> int:
    mList = []
    for num in nums:
        if not mList or mList[-1] < num:
            mList.append(num)
        else:
            # 二分查找
            i = bisect_left(mList, num)
            mList[i] = num
    return len(mList)

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。