首先需要两个数组:
temp存储原数组内容的最长递增子序列(长度同最终结果,但并非要求的最长递增子序列,需要通过nums数组进行判断);
nums存储原数组内容进入temp时的“虚拟”下标(所谓虚拟,指的是并非原数组所有内容都能进入temp,这是肯定的,但nums记录的内容确实与原数组一一对应,目的是通过nums数组回溯到原数组寻找正确的最长递增子序列),即原数组内容在temp中的下标值,因此nums数组的最大值是temp数组长度-1,即要求的最长递增子序列长度-1。
其次采用贪心+二分法的思想。
具体而言,贪心体现在判断原数组内容进入temp时存放的位置以及是否存放,因为当temp数组最后一个元素最小时,扩展更长子序列的可能性更大,因此需要进行三种判断:arr.at(i)>temp[tempindex] OR arr.at(i)==temp[tempindex]
OR arr.at(i)<temp[tempindex]。
针对第一种情况,直接将原数组内容arr[i]存入temp,temp长度加1,并更新nums,记录此时temp下标;
针对第二种情况,无需将原数组内容arr[i]存入temp,故temp长度不变,但需要更新nums,其值仍是temp最后一个元素的下标;
针对第三种情况,需要先将原数组内容arr[i]与temp当前全部元素进行比较,找到合适位置与temp该位置原值进行替换,此处采用了二分思想,更快速地找到替换位置,故temp长度不变,但需更新nums,记录此时该值在temp中的下标。
最后,通过nums数组内容与原数组一一对应,构造正确的最长递增子序列,其长度同temp长度,也即nums最大值加1,故从nums最大值开始(从右往左),依次递减地寻找第一次出现的结果(即正确最长递增子序列的下标值,直到下标值为0),根据其在nums的位置对应到原数组arr相同位置的数值,即可得到正确的最长递增子序列。

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        //以下程序只找到最长递增子序列的长度
        /*
        int Len=0;
        vector<int> dp(arr.size(),1);
        for(int i=0;i<arr.size();++i)
        {
            for(int j=0;j<i;++j)
            {
                if(arr.at(j)<arr.at(i))
                {
                    dp[i]=max(dp[i], dp[j]+1);
                    Len=max(dp[i],Len);
                }
            }
        }
        return Len;
        */


        //贪心+二分法,贪心体现在判断新元素是否进入temp数组,即temp最后一个元素越小,则可能扩展地更长
        vector<int> nums(arr.size());//记录原数组内容在temp数组的下标,即位置i对应的递增序列长度-1
        vector<int> temp(arr.size());//定义未知长度数组时出现bug,存放递增子序列内容,但并非实际输出内容
        int tempindex=0;//记录当前temp数组下标
        nums[0]=0;
        //int maxindex=0;//原本想记录nums数组最大值,但实际上其最大值即为tempindex
        temp[tempindex]=arr.at(0);//原数组第一个元素进入temp
        for(int i=1;i<arr.size();++i)
        {
            int left=0,right=tempindex;//temp数组在左右指针,通过二分法判断arr[i]与temp内容比较
            if(arr.at(i)>temp[tempindex])
            {//新加入的元素大于temp中所有值,则直接加入,并修改nums值
                ++tempindex;
                temp[tempindex]=arr.at(i);
                nums[i]=tempindex;
            }
            else if (arr[i]==temp[tempindex])
            {//相等时需要单列出来,即对temp数组不作改动,但对nums数组需要记录其下标,同前一个
                nums[i]=tempindex;
            }
            else 
            {//arr[i]与temp内容作比较时采用了二分思想
                while(left<=right)
                {
                    int mid=(left+right)/2;
                    if(temp[mid]>arr.at(i))
                        right=mid-1;
                    else
                        left=mid+1;
                }
                temp[left]=arr.at(i);//将新值加入到temp,保证递增
                nums[i]=left;//此时tempindex=left
            }
        }
        vector<int> res(tempindex+1);//temp数组记录的递增子序列长度即为最终结果的序列长度
        for(int i=nums.size()-1;i>=0;--i)
        {//从右往左依次寻找第一次出现递减的下标值,其位置对应的原数组内容即为真正的递增子序列
            if(nums.at(i)==tempindex)
            {
                res[tempindex]=arr.at(i);
                --tempindex;
            }
        }
        return res;
    }
};