体现贪心的“贪”

寻找一个最长的递增子序列，应用贪心算法。
什么样的递增子序列最长，或者说有机会最长？子序列的前面的数字越小，往后面拓展时越有可能得到更长的递增子序列。
以题目为例[2,1,5,3,6,4,8,9,7]
我们首先定义一个向量dp，dp的长度代表当前最长的递增子序列长度。dp的元素选取体现我们的“贪心”
遍历原数组arr，放第一个元素到dp中；dp=[2]，这时没什么好说的；
然后放arr的第二个元素。第二个元素比dp末尾的2要小，这时候我们直接把2换成1, 因为就目前来看，最长的递增子序列长度只能是1,但是我们要把2换成更小的1,这样子往后面遍历时候，更容易找到比1大的元素，也即找到更长的递增子序列。此时dp变成了[1]；
然后我们再考虑arr的第三个元素5，因为5比dp的尾元素1要大，直接把5加入到dp的末尾；
然后再考虑3，3比5小，那么我们就把3替换掉dp中从左往右第一个比3大的元素。这时元素3并没有改变最长递增子序列的长度，而是蛰伏在dp中，如果arr后面有3.1,3.2,3.3,3.4（仅作举例）的话，3是可以发挥作用的。
以此类比，就可以得到最长递增子序列的长度。为了得到具体的子序列，还需要另一个与arr等长的向量place，place记录的是arr对应位置的元素在dp中的位置。
具体代码如下

vector<int> LIS(vector<int>& arr) {
        if(arr.size()<=1)return arr;
        vector<int> dp;
        vector<int> place;
        dp.push_back(arr[0]);
        place.push_back(1);
        for(int i=1;i<arr.size();i++){
            if(arr[i]>=dp.back()){
                dp.push_back(arr[i]);
                place.push_back(dp.size());
            }
            else{
                for(int j=0;j<dp.size();j++)
                    if(dp[j]>arr[i]){dp[j]=arr[i];place.push_back(j+1);break;}
            }
        }
        vector<int> result(dp.size());
        for(int i=dp.size();i>0;i--){
            for(int j=place.size()-1;j>=0;j--){
                if(place[j]==i){result[i-1]=arr[j];place.pop_back();break;}
                place.pop_back();
            }
        }
        return result;
    }