体现贪心的“贪”
最长递增子序列
http://www.nowcoder.com/questionTerminal/9cf027bf54714ad889d4f30ff0ae5481
寻找一个最长的递增子序列,应用贪心算法。
什么样的递增子序列最长,或者说有机会最长?子序列的前面的数字越小,往后面拓展时越有可能得到更长的递增子序列。
以题目为例[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; }