Longest Increasing Subsequence

LeetCode #300

Description:

Given an unsorted array of integers, find the length of longest increasing subsequence.

Your algorithm should run in O(n2) complexity.

Example:

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.

Idea:

Similar to Longest Increasing Path in Matrix, which is 2D DP. This is the 1D DP version.

Use this equation: DP[i] = max(DP[j] + 1) for all j>i. Then find the largest value among DP[i].

Code:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;

        int n=nums.size();
        vector<int> DP(n, 0);
        DP[n-1]=1;

        int max_len=0;
        for(int i=0; i<n; ++i){
            max_len = max(max_len, findLongest(nums, i, DP));    
        }

        return max_len;
    }

    int findLongest(const vector<int>& nums, int i, vector<int>& DP){
        if(DP[i]!=0) return DP[i];

        int n=nums.size();
        int longest=0;
        for(int j=i+1; j<n; ++j){
            if(nums[i]<nums[j])
                longest = max(longest, findLongest(nums, j, DP));
        }
        DP[i] = longest+1;
        return DP[i];
    }
};