首先需要两个数组：
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;
    }
};