Solution of Leetcode problem (Longest ascending subsequence Problem)

define

LIS (Longest Increasing Subsequence) the sequence BI of the Longest Increasing Subsequence, when B1 < B2 <… When < bS, we say the sequence is ascending. For a given sequence (A1, A2… , aN), we can get some ascending subsequences (AI1, AI2… , aiK), where 1 <= i1 < i2 <… < iK <= N. For example, for the sequence (1, 7, 3, 5, 9, 4, 8), there are ascending subsequences, such as (1, 7), (3, 4, 8), and so on. The longest of these subsequences is 4, such as subsequences (1, 3, 5, 8). Your task is to find the length of the longest ascending subsequence for a given sequence.

Leetcode 300. Longest ascending subsequence

Analysis of the problem solving

Violent solution

• Select all subsequences for judgment. O((2^n)*n)

Dynamic programming solution

State definition

LIS(I) represents the length of the longest ascending subsequence ending in the ith digit. LIS(I) represents the range of [0… I] and selects the length of the longest ascending subsequence that nums[I] can obtain.

State transition

LIS(i) = max(1+LIS(j) if nums[i]>nums[j]) (j<i)

Copy the code

Code implementation

Recursive plus mnemonic search

class Solution {

// In the range [0... index], select the length of the longest ascending subsequence that nums[index] can obtain.
private:
    vector<int> memo;
    int searchLIS(vector<int>& nums, int index){
        if (index == 0) {return 1;
        }
        
        if(memo[index] ! =- 1) {return memo[index];
        }

        int res = 1;
        for (int i = 0; i < index; i++){
            if (nums[index] > nums[i]){
                res = max(res, 1 + searchLIS(nums, i));
            }

        }
        memo[index] = res;
        return res;
    }

public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {return 0;
        }
        memo = vector<int>(n, - 1);
        int res = - 1;
        for(int i = 0; i < n; i++){
            res = max(res, searchLIS(nums, i));
        }
        returnres; }};Copy the code

Using dynamic programming

class Solution {

public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {return 0;
        }
        // Memo [index] indicates the length of the longest ascending subsequence that nums[index] can obtain in the range [0... index].
        vector<int> memo(n, 1);
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    memo[i] = max(memo[i], memo[j] + 1); }}}int res = - 1;
        for(int i = 0; i < n; i++){
            res = max(res, memo[i]);
        }
        returnres; }};Copy the code

Similar to the topic

• leetcode 376

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato technology small stack and gold digging home page

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan