300 Longest Increasing Subsequence (Medium)

第一次做题思路201511092250
1.采用map存储，key为nums[i]，value为以nums[i]为结尾的最大递增子序列的长度
2.采用map里面的lower_bounder函数直接找出第一个大于或等于nums[i]的位置，位置ite–，然后遍历前面的数，找出比nums[i]的数里面，长度len最长的，令nums[i]的最大递增子序列的长度为len+1
3.AC时间为148ms

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?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
		map<int, int> m;
		int maxLength = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			map<int, int>::iterator ite = m.lower_bound(nums[i]);
			if (ite == m.begin())
				m[nums[i]] = 1;
			else
			{
				ite--;
				int tmpMax = ite->second + 1;
				for (; ite != m.begin(); ite--)//寻找比nums[i]小的数，并在这些数里面，找出长度最大的
					tmpMax = max(tmpMax, ite->second + 1);
				if (ite == m.begin())//寻找比nums[i]小的数，并在这些数里面，找出长度最大的
					tmpMax = max(tmpMax, ite->second + 1);
				m[nums[i]] = tmpMax;
			}
			maxLength = max(maxLength, m[nums[i]]);
		}
		return maxLength;
	}
};