LeetCode之300—-Longest Increasing Subsequence

题目：

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

题目大意：

求数组中最长递增子序列的长度，如序列[10, 9, 2, 5, 3, 7, 101, 18]，则最长递增子序列是[2, 3, 7, 101]，所以程序返回4。要求O（nlogn）的时间复杂度。

分析：

本题原本是老师让做的课后题，到LeetCode上一搜之后发现有这道题，顺便也就把它做了。本题可用动态规划思想做。

1、扫描原数组中的数，先判断是否大于结果数组中的最后一个（最大数），如果大于结果数组中的最大数则将这个数加入结果数组。否则，在结果数组中寻找第一个大于扫描数的数字下标，然后替换。

   ２、重复上述步骤直到把原数组遍历完。

        3、查找的方法可以使用二分法查找，还需要将原数组遍历一遍。所以时间复杂度为O（nlogn）。

        4、本思路只能求解出长度，不能解出序列。

代码：

class Solution {
public:
    //二分法查找第一个大于tar的数字，返回其下标
    std::vector<int>::size_type BinarySearch(const std::vector<int> &nums, const int &tar)
    {
        int hig = nums.size() - 1;
        int low = 0;
        int mid;
        
        while (low <= hig) {
            mid = (hig + low) / 2;
            if (tar == nums[mid]) {
                return mid;
            } else if (tar < nums[mid]) {
                hig = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return low;
    }
    
    int lengthOfLIS(std::vector<int>& nums) {
        std::vector<int> result;
        std::vector<int>::size_type tmp, index;
        
        if (nums.size() == 0) {
            return 0;
        }
        
        result.push_back(nums[0]);
        //扫描原数组
        for (int i = 1; i != nums.size(); ++i) {
            tmp = nums[i];
            //如果数字大于结果数组中的最大数则直接加入数组
            if (tmp > result[result.size() - 1]) {
                result.push_back(tmp);
            } else {  //否则
                index = BinarySearch(result, tmp);     //寻找第一个比它大的数
                result[index] = tmp;    //替换
            }
        }
        return result.size();     //返回结果长度
    }
};