dp14-17 longest ascending subsequence - original title + variant

dp 14 longest ascending subsequence (1)

Topic description

describe

Given an array arr of length n, find the length of its longest strictly ascending subsequence.

The so-called subsequence refers to a new array formed by deleting some numbers (or not deleting) from an array. For example [1,5,3,7,3] array, its subsequences are: [1,3,3], [7] and so on. But [1,6], [1,3,5] are not its subsequences.

We define a sequence to be strictly ascending if and only if the sequence does not have two subscripts ii and jj such that i<ji<j and arr_i \geq arr_jarr**i≥arr**j.

data range:
0 ≤ n ≤ 1000 , ∣ a r r i ∣ ≤ 1 0 9 0 \leq n \leq 1000 , |arr_i| \le 10^9 0≤n≤1000,∣arri​∣≤109
Requirements: time complexity O(n^2) O(n2), space complexity O(n)O(n)

Enter description:

Enter a positive integer n on the first line, indicating the length of the array

The second line enters n integers representing each element of the array.

Output description:

output the length of the longest strictly ascending subsequence

input sample
7
6 3 1 5 2 3 7
 output
4

leetcode version description

Given an array of integers nums , find the length of the longest strictly increasing subsequence in it.

A subsequence is a sequence derived from an array that removes (or does not remove) elements from the array without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

enter: nums = [10,9,2,5,3,7,101,18]
output: 4
 Explanation: The longest increasing subsequence is [2,3,7,101],So the length is 4 .
enter: nums = [7,7,7,7,7,7,7]
output: 1

Thought analysis:

This question is a standard linear dynamic programming question. First consider how the state is defined. If defined as the length of the longest strictly ascending subsequence of the first i elements, then we would not be able to take advantage of the recorded value, as it only states the longest length. But it doesn't say how the sequence begins and ends. We cannot give it a specific judgment, and we have not recorded other information about this sequence.

So here we can impose an additional limit on the state, which is the length of the longest strictly ascending subsequence of the previous i ending with the i-th element. After this addition, whenever we read in a new element, we can look up the previous dp array, find which sequence this new element can be added to, and count the maximum value. All values ​​are calculated bottom-up.

As for the remaining interceptor missiles, it is obvious that this question changes from increasing to decreasing, and it is enough to calculate a minimum number.

The chorus formation is the longest ascending subsequence in both directions, then count the number of people, get k, and subtract it.

Envelope nesting is a two-dimensional longest ascending subsequence, which can be calculated after sorting.
(The longest ascending subsequence can also add two points greedily, only the dp solution is given here)

Specific code implementation:

/*dp14*/
#include <bits/stdc++.h>
using namespace std;
    int n;
    int a[1001];
    int dp[1001];
    //Define dp(i) as the length of the longest strictly ascending subsequence of the sequence ending at the ith element of the first i elements
    //In this case, each subsequent addition of an element can increase the length of the answer
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int maxN = INT_MIN;
    for(int i = 0; i < n; ++i) dp[i] = 1;
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < i; ++j) {
            if(a[i] > a[j]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxN = max(maxN, dp[i]);
    }
    // for(int i = 0; i < n; ++i) {
    //     printf("%d", dp[i]);
    // }
    //cout << endl;
    printf("%d", maxN);
    return 0;
}

dp 15 interceptor missile

/*dp15*/
//Longest ascending/descending subsequence + number of sequences
#include <bits/stdc++.h>
using namespace std;
    int n;
    int a[1001];
    int dp[1001];
    //Define dp(i) as the length of the longest strictly ascending subsequence of the sequence ending at the ith element of the first i elements
    //In this case, each subsequent addition of an element can increase the length of the answer
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int maxN = INT_MIN;
    int c = 1;

    vector<int> s;
    s.push_back(a[0]);
    vector<int>::iterator it;
    for(int i = 0; i < n; ++i) dp[i] = 1;
    for(int i = 1; i < n; ++i) {
        it = lower_bound(s.begin(), s.end(), a[i]);//Note that it must be lower_bound so that elements that are exactly equal to a[i] can be counted
        if(it == s.end()) {//new value added
            s.push_back(a[i]);
        } else { // Update the current value when it is less than 
            *it = a[i];
        }
        for(int j = 0; j < i; ++j) {
            if(a[i] <= a[j]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxN = max(maxN, dp[i]);
    }
    //  for(int i = 0; i < n; ++i) {
    //      printf("%d", dp[i]);
     // }
    //cout << endl;
    // for(int v : s) {
    //     cout << v << ' ';
    // }
    // cout << endl;
    printf("%d\n%d", maxN, s.size());
    return 0;
}

dp 16 chorus formation

/*dp16*/
//Longest ascending subsequence * 2
#include <cstdio>
#include <iostream>

int max(int x, int y) {
    if(x < y) return y;
    return x;
} 
    int n;
    int a[1001];
    
    int left[1001];
    int right[1001];
    //Define dp(i) as the length of the longest strictly ascending subsequence of the sequence ending at the ith element of the first i elements
    //In this case, each subsequent addition of an element can increase the length of the answer
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; ++i) 
        left[i] = right[i] = 1;
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < i; ++j) {
            if(a[i] > a[j]) {
                left[i] = max(left[i], left[j]+1);
            }
        }
    }
    for(int i = n-1; i >= 0; --i) {
        for(int j = n-1; j > i; --j) {
            if(a[i] > a[j]) {
                right[i] = max(right[i], right[j]+1);
            }
        }
    }

    // for(int i = 0; i < n; ++i) {
    //     std::cout << left[i] << ' ';
    // }
    // std::cout << std::endl;
    // for(int i = 0; i < n; ++i) {
    //     std::cout << right[i] << ' ';
    // }
    int maxN = 0;
    for(int i = 0; i < n; ++i) {
        maxN = max(maxN, left[i] + right[i]);
    }
    printf("%d", n - maxN + 1);
    return 0;
}

dp 17 envelope nesting

/*dp17 Envelope Nesting*/
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[1001];
bool cmp(const pair<int, int>& x, const pair<int, int>& y) {
    if (x.first != y.first) {
        return x.second < y.second;
    }
    return x.first < y.first;
}
int main() {
    scanf("%d", &n);
    vector<pair<int, int> > a(n, pair<int, int>(0, 0));
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &a[i].first, &a[i].second);
    }
    sort(a.begin(), a.end(), cmp);
    
    int maxN = 1;
    for (int i = 0; i < n; ++i) dp[i] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[i].first > a[j].first && a[i].second > a[j].second) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxN = max(maxN, dp[i]);
    }
    // for(int i = 0; i < n; ++i) {
    //     printf("%d", dp[i]);
    // }
    //cout << endl;
    printf("%d\n", maxN);
    return 0;
}
/*dp17 Envelope Nested Dichotomous Sort similar to leetcode-757. Set intersection size to at least 2*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
int endsArr[N];

struct Letter {
    int height, width;
    bool operator < (const Letter& L) const {
        return height != L.height ? height < L.height: width > L.width;
    }
    int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int h, w;
        scanf("%d%d", &h, &w);
        letters[i] = {h, w};
    }
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    sort(letters, letters + n);
//     for(int i = 0; i < n; i++) cout << letters[i].height << " " << letters[i].width << endl;
    endsArr[0] = letters[0].width;
    int size = 0;
    for (int i = 1; i < n; i++) {
        int index = lower_bound(endsArr, endsArr + size + 1,
                                letters[i].width) - endsArr;
        if (index == size + 1) {
            size++;
        }
        endsArr[index] = letters[i].width;
    }
    printf("%d\n", size + 1);
    return 0;
}

Tags: Algorithm Dynamic Programming Graph Theory

Posted by cheese on Fri, 23 Sep 2022 21:58:32 +0300