Longest Increasing Subsequence

题目：

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

分析：

如何用binary search做这道题目？？？

state: f[i] means longest LIS from 0 to i, including i

function: f[i] = max(f[j], j from 0 to i - 1) + 1, if nums[i] >= nums[j]

initialization: f[0] = 1

answer: max(f[i])!!

解法：

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        // write your code here

        if (nums.size() == 0) {
            return 0;
        }

        int n = nums.size();
        vector<int> res(n, 0);
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            int maxLIS = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] >= nums[j]) {
                    maxLIS = max(maxLIS, res[j] + 1);
                }
            }
            res[i] = maxLIS;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, res[i]);
        }
        return ans;
    }
};