A typical O(n^2) solution uses dynamic programming. Let‘s use lens[j] to denote the length of the LIS ending with nums[j]. The state equations are
lens[0] = 1
lens[j] = max_{i = 0, 1, 2, ..., j - 1}(lens[j], lens[i] + 1)
Then the length of the LIS of nums is just the maximum value in lens. The code is as follows.
1 class Solution { 2 public: 3 int lengthOfLIS(vector<int>& nums) { 4 if (nums.empty()) return 0; 5 int n = nums.size(), ml = 1; 6 vector<int> lens(n, 1); 7 for (int j = 1; j < n; j++) { 8 for (int i = 0; i < j; i++) 9 if (nums[j] > nums[i]) 10 lens[j] = max(lens[j], lens[i] + 1); 11 ml = max(ml, lens[j]); 12 } 13 return ml; 14 } 15 };
The O(nlogn) solution will come out soon...
[LeetCode] Longest Increasing Subsequence
原文：http://www.cnblogs.com/jcliBlogger/p/4934562.html