LintCode 76: Longest Increasing Subsequence(가장 일반적인 DP 문항)

해법1:DP.시간 복잡도 O (n^2).코드는 다음과 같습니다.

class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector &nums) {
        int numSize = nums.size();
        if (numSize <= 1) return numSize;
        
        vector DP(numSize, 0);
        int g_maxLen = 0;
        int g_maxId = 0;
    
        DP[0] = 1;
        for (int i = 1; i < numSize; ++i) {
            int maxLen = 0;
            int maxId = 0;
            
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (DP[j] > maxLen) {
                        maxLen = DP[j];
                        maxId = j;
                    }
                }
            }
            
            DP[i] = maxLen + 1;
        
            if (DP[i] > g_maxLen) {
                g_maxLen = DP[i];
                g_maxId = i;
            }
        }
        
        return g_maxLen;
    }
};

해법 2: Binary Search.시간 복잡도 O (nlogn).새로운 array B를 사용합니다. [n + 1].For example, A = {2,3,1} B = {-INF, INF, INF, INF}
A의 모든 요소 a를 훑어보고 B의 첫 번째 큰 위치를 찾으며 이 위치의 값을 a로 설정합니다.예를 들어, B = {-INF, 2, INF, INF} B = {-INF, 2, 3, INF} B = {-INF, 1, 3, INF}
마지막으로 B의 요소를 뒤로 이동하여 첫 번째 비INF 값을 찾습니다. 위치가 LIS입니다.예를 들어, B[2] = 3, then LIS = 2.
코드는 다음과 같습니다(9장 참조).

#include 
#include 
#include

using namespace std;

// find the first number > num
int binarySearch(vector & minLast, int num) {
    int start = 0, end = minLast.size() - 1;
    while (start + 1 < end) {
        int mid = (end - start) / 2 + start;
        if (minLast[mid] < num) {
            start = mid;
        } else {
            end = mid;
        }
    }

    return end;
}

int longestIncreasingSubsequence(vector & nums) {
    vector minLast(nums.size() + 1, 0);
    minLast[0] = INT_MIN;

    for (int i = 1; i <= nums.size(); i++) {
        minLast[i] = INT_MAX;
    }

    for (int i = 0; i < nums.size(); i++) {
        // find the first number in minLast >= nums[i]
        int index = binarySearch(minLast, nums[i]);
        minLast[index] = nums[i];
    }

    for (int i = nums.size(); i >= 1; i--) {
        if (minLast[i] != INT_MAX) {
            return i;
        }
    }

    return 0;
}

int main()
{
  //  vector nums = {2, 3, 1, 7, 6, 4, 8};
    vector nums = {2, 3, 1};
    int result;
    result = longestIncreasingSubsequence(nums);
    cout<