Longest Increasing Subsequence

LeetCode #300


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

Your algorithm should run in O(n2) complexity.


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.


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].


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

        int n=nums.size();
        vector<int> DP(n, 0);

        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){
                longest = max(longest, findLongest(nums, j, DP));
        DP[i] = longest+1;
        return DP[i];

results matching ""

    No results matching ""