Leetcode longest sequence

The longest sequence

300. The longest increasing subsequence 【 secondary 】

• Method 1 ： Dynamic programming
  Time complexity ：O(n^2)
  Spatial complexity ：O(n)

1、 determine dp Array and its meaning

• dp[i] Express 0~i Length of the longest ascending subsequence of the index

2、 Determine the state transfer equation

• if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j]+1);

3、dp initialization

• dp[i] = 1;, as long as nums There's a length , At least for 1

class Solution {
    
public:
    int lengthOfLIS(vector<int>& nums) {
    
        if(nums.size() <= 1) return nums.size();
        // dp initialization 
        vector<int> dp(nums.size(), 1);
        
        int maxLen = 0;
        for (int i = 1; i < nums.size(); ++i) {
     // With i At the end of the nums The longest ascending subsequence of 
            for (int j = 0; j < i; ++j) {
    
                if (nums[j] < nums[i]) {
    
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

Method 2 ： greedy + Two points search
Time complexity ：O(nlogn)
Spatial complexity ：O(n)

674. The longest continuous increasing sequence 【 Simple 】

Train of thought ： Dynamic programming
Time complexity ：O(n)
Spatial complexity ：O(n)

1、 determine dp Array and its subscript meaning

• dp[i] It's the index 0~i Time continuous increment subsequence length

2、 Determine the recurrence formula

• if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;

3、dp initialization

• vector<int> dp(nums.size(), 1);

class Solution {
    
public:
    int findLengthOfLCIS(vector<int>& nums) {
    
        if (nums.size() <= 1) return nums.size();
        
        int maxLen = 1;
        vector<int> dp(nums.size() ,1);
        for (int i = 1; i < nums.size(); i++) {
    
            if (nums[i] > nums[i-1])  //  Continuous record 
                dp[i] = dp[i-1] + 1;

            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

• Train of thought two ： greedy
  Time complexity ：O(n)
  Spatial complexity ：O(1)

class Solution {
    
public:
    int findLengthOfLCIS(vector<int>& nums) {
    
        if (nums.size() <= 1) return nums.size();
        
        int maxLen = 1;
		int count = 1;
        for (int i = 1; i < nums.size(); i++) {
    
            if (nums[i] > nums[i-1])   count++;
            else count = 1;
               
			maxLen = max(maxLen, count);
        }
        return maxLen;
    }
};

Train of thought three ： Double pointer
Time complexity ：O(n)
Spatial complexity ：O(1)

class Solution {
    
public:
    int findLengthOfLCIS(vector<int>& nums) {
    
        if (nums.size() <= 1) return nums.size();
        
        int maxLen = 1;
		int start = 0;
        for(int end = 1; end < nums.size(); ++end){
    
            if(nums[end] <= nums[end-1]){
    
                maxLen = max(maxLen, end - start);
                start = end;
            }
        }
        // The last section 
        if(nums.size() - start > maxLen) maxLen = nums.size() - start;
        return maxLen;
    }
};

718. Longest repeating subarray 【 secondary 】

Ideas ： Dynamic programming
Time complexity ：O(mn)
Spatial complexity ：O(mn)

1、 determine dp Array and its subscript meaning

• dp[i][j]： By subscript i-1 At the end of the A,j-1 At the end of the B, Their longest repeating subarray length

2、 Determine the recurrence formula

• dp[i][j] = dp[i-1][j-1] + 1;

3、dp initialization

• dp[i][0] = 0;
• dp[0][j] = 0;

class Solution {
    
public:
    int findLength(vector<int>& A, vector<int>& B) {
    
        vector<vector<int>> dp (A.size() + 1, vector<int>(B.size() + 1, 0));
        int maxLen = 0;
        for (int i = 1; i <= A.size(); i++) {
    
            for (int j = 1; j <= B.size(); j++) {
    
                if (A[i - 1] == B[j - 1]) {
    
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                
                maxLen = max(maxLen, dp[i][j]);
            }
        }
        return maxLen;
    }
};

Train of thought two ： Space optimization , Scrolling array

class Solution {
    
public:
    int findLength(vector<int>& A, vector<int>& B) {
    
        vector<int> dp(vector<int>(B.size() + 1, 0));
        int maxLen = 0;
        for (int i = 1; i <= A.size(); i++) {
    
            for (int j = B.size(); j > 0; j--) {
    
                if (A[i - 1] == B[j - 1]) {
    
                    dp[j] = dp[j - 1] + 1;
                } 
                else dp[j] = 0; //  Note that when there is inequality here, there should be fu 0 The operation of 
                
                maxLen = max(maxLen, dp[j]);
            }
        }
        return maxLen;
    }
};

1143. Longest common subsequence 【 secondary 】

• Ideas ： Dynamic programming
  Time complexity ：O(mn)
  Spatial complexity ：O(mn)

1、 determine dp Array and subscript meaning

• dp[i][j]： The index for 0-i Of text1 And 0-j Of text2 The longest common subsequence of

2、 Determine the recurrence formula

• if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
• if(text1[i-1] != text2[j-1]) dp[i][j] != max(dp[i-1][j], dp[i][j-1]);

3、dp initialization

• vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), 0));

class Solution {
    
public:
    int longestCommonSubsequence(string text1, string text2) {
    
        vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));

        for(int i = 1; i <= text1.size(); i++){
    
            for(int j = 1; j <= text2.size(); j++){
    
                if(text1[i-1] == text2[j-1]){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
    
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};