在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的 第63题：数组染色 的题目解析，具体如下：
题目描述
等级：中等
知识点：DP、LIS
查看题目：数组染色
codancer现在有一个长度为n的数组a,对于每个这个数组的每个数字，我们必须染上颜色，但是codancer有一个限制条件:如果i<j并且a[i]<a[j],那么a[i]和a[j]必须染同一种颜色,否则则染不同的颜色。现在codancer想知道最少几种颜色才能把整个数组染完颜色。
输入一个正整数n和数组a。
（1<=n<=100000,0<=a[i]<=1000000000）.
输出最少需要的颜色种类数。
示例1
输入：
5
[2,1,4,5,3]
输出：
2
注意
把a[1],a[3],a[4]染同一种颜色，把a[2]和a[5]染成另外一种颜色。
解题思路
大致思路：可以采用链表的思想，定义一个数组temp来存放每个递增的子串，题目需要求出最少的递增子串有多少个，采取的思路是递增的子串越密集越好，即若有2，4，3，5。那么我最优选择的是密集子串2，3和4，5.而不是2，4和3，5；即使对这个测试用例来说，答案都是一样的，但是就题目而言，密集子串是最优的选择。
具体思路：定义一个数组temp来存放每个递增的子串，那么我先将第一个元素放在temp数组的第一个位置，从i=1开始遍历x数组，将x[i]与temp数组的第一个元素开始比较（j=0），如果x[i]>temp[j],那么我就将x[i]元素链接在temp[j]元素后面，又因为这是个数组，不是链表，而且链接后temp[j]值再也用不上，和链表的最后一个元素比较，因此可以直接覆盖temp[j]元素，即temp[j]=x[i]。我说的链接如下图所示
可以发现，每次比较都是和链表最后一个元素比较，所以前面的元素可以覆盖，如下面的直接覆盖法，也是用数组实现，很简单。而且还可以发现，temp数组永远是递减的，这样也满足密集子串，因为从上往下走，找到满足的即可停止，不需要继续往下。最终，temp数组有几个元素，答案就是多少。可以用ans一致指向temp数组的最后一个元素的位置。
完全理解本解法需要理解我定义的密集子串和链接法转直接覆盖等概念。好好理解一下，很简单，有什么问题可以在评论区交流。
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：数组染色
