Leetcode动态规划：300.longest-increasing-subsequence（最长递增子序列）

300. 最长递增子序列

最近一直在攻克动态规划的题，Leetcode的简单题已经刷完，现在冲中等题，这道题算是一个比较经典的题吧，独立完成，虽然花了两个多小时，但收获很多；

思路：动态规划首先要找到状态，其次建立状态转移方程；此处状态无疑就是当前子序列的长度以及子序列的尾数，因为这样才能动态改变状态，比较来了一个大的数字，我可以让子序列长度+1，然后把子序列的尾数更新为它，当然这只是个简单思路，里面还有很多细节问题；

int lengthOfLIS(vector<int> &nums){int len = nums.size();if (len < 2)return len;// 先跳过前面的递减序列（如果存在的话）int start = 0;while (start + 1 < len && nums[start] >= nums[start + 1]){start++;}// 核心部分vector<int> vec;// vec[i]=j表示以j结尾的子序列的长度为i，因为这里每次子序列的长度只能增加1，所以用数组下标很合适vec.push_back(0);// vec[0]=0 没意义vec.push_back(nums[start]); // 把第一个元素放进去int cur = 1;//cur表示当前vec数组的长度（不含vec[0] 没意义）// 对于nums的元素nums[i]for (int i = start; i < len; i++){bool flag = true; //flag表示能否在vec中找的比nums[i]小的元素// 在vec中找，优先从子序列长度大的开始找，就是cur开始，依次--，直到找到for (int j = cur; j >= 1; j--){// 找到vec[j]比nums[i]小，并且子序列长度为jif (vec[j] < nums[i]){// 如果j是最长长度，那么我加入nums[i]后必要最长长度+1，所以这里push_backif (j + 1 > cur){vec.push_back(nums[i]);cur++;}// 否则，判断相同长度，这个nums[i]是否比vec[j+1]小，如果小，那么用它代替为vec[j+1](为什么是j+1？因为加入nums[i]后长度要+1)else if (vec[j + 1] > nums[i])vec[j + 1] = nums[i];// 置flag=false，表示找到了比nums[i]小的元素flag = false;break;}}// 如果没找到比nums[i]小的元素，那么说明nums[i]要单独作为一个子序列的起始元素，长度为1if (flag){// 这时同样将它与vec[1]的元素比较，放入最小的才能保证之后有更大的机会组成最长子序列if (vec[1] > nums[i])vec[1] = nums[i];}}return cur; //返回vec的长度即可，表示最长递增子序列的长度}