[LintCode] 最长上升子序列

动态规划：

lis[i] = max_{j = 0, 1, ..., i - 1, nums[j] < nums[i]} lis[j] + 1

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: The integer array
 5      * @return: The length of LIS (longest increasing subsequence)
 6      */
 7     int longestIncreasingSubsequence(vector<int> nums) {
 8         // write your code here
 9         vector<int> lis(nums.size(), 1);
10         int maxlen = 0;
11         for (int i = 1; i < (int)nums.size(); i++) {
12             for (int j = 0; j < i; j++)
13                 if (nums[j] <= nums[i] && lis[j] + 1 > lis[i])
14                     lis[i] = lis[j] + 1;
15             maxlen = max(maxlen, lis[i]);
16         }
17         return maxlen;
18     }
19 };