線上程式設計介紹
阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：
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數組的最後一個元素的位置。
完全了解本解法需要了解我定義的密集子串和連結法轉直接覆寫等概念。好好了解一下，很簡單，有什麼問題可以在評論區交流。
看完之後是不是有了想法了呢，快來練練手吧>>
