Dynamic programming (V)

One 、 Longest ascending subsequence ( One )

solution : Dynamic programming

• use dp[i] Representation to element iii At the end , The length of the longest subsequence , Initialize to 1, Because only arrays have elements , At least one is incremental .
• The first layer traverses each position of the array , obtain n A subarray of length .
• The second layer traverses the corresponding subarray to find the corresponding element iii The longest increment sequence length at the end , Maximum during maintenance .
• For each to iii At the end of the subarray , If an element is encountered during traversal j Less than the closing element , It shows that the subsequence ending with this element plus the last element of the subarray is also strictly incremental , So the transfer equation is dp[i]=dp[j]+1

class Solution {
    
public:
    int LIS(vector<int>& arr) {
    
        // Dynamic programming auxiliary array for setting the length and size of the array 
        vector<int> dp(arr.size(), 1); 
        int res = 0;
        for(int i = 1; i < arr.size(); i++){
    
            for(int j = 0; j < i; j++){
    
                // Probably j Not the biggest thing you need , Therefore need dp[i] < dp[j] + 1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
    
                    //i Point to j It's a little big , Theoretically dp To add 1
                    dp[i] = dp[j] + 1; 
                    // Find the maximum length 
                    res = max(res, dp[i]); 
                }
            }
        }
        return res;
    }
};

Time complexity ：O(n^2) among n Is array length , Two layer ergodic loop
Spatial complexity ：O(n), Auxiliary array dp Space

Two 、 The maximum sum of successive subarrays

Solution 1 : Dynamic programming ( recommend )

Because there are positive and negative charges in the array 0, So one number at a time , Do you want to add it to the continuous subarray we are looking for , It's a problem. , It's possible that it will be bigger , It's possible to join a smaller , And we want a continuous maximum , Therefore, this kind of stateful transition problem can be considered as dynamic programming .

• It can be used dp The array represents the following symbol iii Is the largest continuous subarray of the end point and .
• Traversal array , Each time a new array element is encountered , Successive subarrays are either added to become larger , Or the element itself is bigger , Or even smaller , We give up when we are younger , So the state transition is dp[i]=max(dp[i−1]+array[i]array[i])
• Because contiguous arrays may break , Each segment can only get the maximum value of that segment , So we need to maintain a maximum .

class Solution {
    
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    
        // Record to subscript i The largest continuous subarray up to and 
        vector<int> dp(array.size(), 0); 
        dp[0] = array[0];
        int maxsum = dp[0];
        for(int i = 1; i < array.size(); i++){
    
            // State shift ： Continuous subarray and maximum 
            dp[i] = max(dp[i - 1] + array[i], array[i]); 
            // Maintenance maximum 
            maxsum = max(maxsum, dp[i]); 
        }
        return maxsum;
    }
};

Time complexity ：O(n), among n Is array length , Traversing the array once
Spatial complexity ：O(n), The length of dynamic programming auxiliary array is n

Solution 2 : Dynamic programming, spatial optimization

We notice that the dynamic programming of method 1 only uses i−1i Information about , There is no information about using the entire auxiliary array , So you can optimize the array .

• We can use two variable iterations instead of arrays .
• Update variables during state transition y, Re update at the end of this cycle x by y You can do that every iteration is the last round dp.
• Traversal array , Just take the maximum value for each comparison .

class Solution {
    
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    
        int x = array[0];
        int y = 0;
        int maxsum = x;
        for(int i = 1; i < array.size(); i++){
    
            // State shift ： Continuous subarray and maximum 
            y = max(x + array[i], array[i]); 
            // Maintenance maximum 
            maxsum = max(maxsum, y); 
            // to update x The state of 
            x = y; 
        }
        return maxsum;
    }
};

Time complexity ：O(n), among n Is array length , Traversing the array once
Spatial complexity ：O(1), Constant level variable , No additional auxiliary space

3、 ... and 、 Longest text substring

Solution 1 : The central expansion method ( recommend )

Palindrome string , It has the characteristics of left-right symmetry , Visit together from beginning to end , The elements encountered are the same . But here we are looking for the longest palindrome string , The length is not known in advance , What do I do ？ The process of judging palindromes is from the beginning to the end to the middle , Then we can find the longest palindrome string in reverse , From the middle to the end , This is the central expansion method .

• Traverses each character of the string .
• Centered on the characters traversed each time （ There are two cases: odd length and even length ）, Continue to expand to both sides .
• If both sides are the same, it is palindrome , It is the character that expands to the maximum length （ Or even two ） The longest palindrome string at the center .
• We compare the longest palindrome substring centered on each character , Take the maximum value .

class Solution {
    
public:
    int fun(string& s, int begin, int end){
    
        // Each center point starts to expand 
        while(begin >= 0 && end < s.length() && s[begin] == s[end]){
     
            begin--;
            end++;
        }
        // Return length 
        return end - begin - 1; 
    } 
    int getLongestPalindrome(string A) {
    
        int maxlen = 1;
        // Center on each point 
        for(int i = 0; i < A.length() - 1; i++) 
            // Divide odd length and even length to extend to both sides 
            maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
};

Time complexity ：O(n^2), among n Is the length of a string , Traverses each character of the string , Each character should be extended O(n)
Spatial complexity ：O(n), Constant level variable , No additional auxiliary space

Solution 2 :manacher Algorithm

Method 1 discusses two cases , The length of substring is odd and even , But in fact, we can add special characters that do not belong to the string , To make all palindromes become odd . At the same time, the above center expansion method has many repeated calculations ,manacher You can optimize ：

• We use it maxpos Represents the last bit of the rightmost bit of the longest palindrome substring known at present , use index Represents the center point of the current longest palindrome substring .
• For a given i Let's find one about it index symmetrical j , It's just index−ji−index In other words j2∗index−i
• i and j The longest palindrome string of is index The part within the palindrome string of should be exactly the same , But the outside part cannot be guaranteed , Of course , The best situation is i and j The palindrome substring range of is very small , This ensures that their palindromes must be exactly the same , There is nothing we can do about the excess , You can only use the central extension manually .
• When calculating the final answer, we need to consider using preprocessing , The length has been doubled , So the result is max(mp[i]-1).

class Solution {
    
public:
    //manacher Algorithm 
    void manacher(string& s, int n, vector<int>& mp){
     
        string ms = "";
        ms += "$#";
        // Preprocessing 
        for(int i = 0; i < n; i++){
     
            // Make it an odd palindrome substring 
            ms += s[i]; 
            ms += '#';
        }
        // The last bit of the rightmost bit of the longest known palindrome substring 
        int maxpos = 0; 
        // The center point of the current longest palindrome substring 
        int index = 0; 
        for(int i = 0; i < ms.length(); i++){
     
            mp[i] = maxpos > i ? min(mp[2 * index - i], maxpos - i) : 1; 
            // Sweep both sides 
            while(ms[i + mp[i]] == ms[i - mp[i]]) 
                mp[i]++;
            // Update location 
            if(i + mp[i] > maxpos){
     
                maxpos = i + mp[i];
                index = i;
            }
        }
    }
    int getLongestPalindrome(string A) {
    
        int n = A.length();
        // Record the length of palindrome substring 
        vector<int> mp(2 * n + 2); 
        manacher(A, n, mp);
        int maxlen = 0;
        // Traversal array 
        for(int i = 0; i < 2 * n + 2; i++) 
            // Find the maximum length 
            maxlen = max(maxlen, mp[i] - 1);  
        return maxlen;
    }
};

Time complexity ：O(n), Are single-layer traversal , Function while The cycle accumulation will not exceed 2n Time
Spatial complexity ：O(n), The length is 2∗n The preprocessed string and length of is 2∗n+2 Array of