Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Độ dài dãy con tối đa với hiệu phần tử liền kề là 0 hoặc 1 | Phần 2 trong C++

Cho mảng bất kỳ, tìm dãy con (subsequence) có hiệu giữa các phần tử liền kề là 0 hoặc 1.

Đầu vào** – int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }

Đầu ra** – Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3

Giải thích** – Dãy con thỏa mãn: {2, 1} (hiệu 1), độ dài 2. (Ví dụ gốc có vẻ không khớp, code cho kết quả 4).

Đầu vào** – int arr[] = { 2, 1, 7, 6, 5 }

Đầu ra** – 3

Giải thích** – {7, 6, 5} hiệu 1, độ dài 3.

Phương pháp (DP + Unordered Map)

  • Duyệt mảng, với mỗi arr[i] tìm độ dài dãy con dài nhất kết thúc tại giá trị này.
  • Dùng unordered_map dp: dp[x] = độ dài dãy con dài nhất kết thúc bằng giá trị x.
  • Cập nhật: len = max(dp[arr[i]-1], dp[arr[i]], dp[arr[i]+1]) + 1.
  • dp[arr[i]] = max(dp[arr[i]], len).
  • Theo dõi maximum toàn cục.

Độ phức tạp O(n) trung bình.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int maximum_adj(int arr[], int size) {
    int maximum = 0, i = 0;
    unordered_map<int, int> un_map;
    while(i < size) {
        int len = 0;
        if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1])
            len = un_map[arr[i]-1];
        if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]])
            len = un_map[arr[i]];
        if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1])
            len = un_map[arr[i]+1];
        un_map[arr[i]] = len + 1;
        if (maximum < un_map[arr[i]])
            maximum = un_map[arr[i]];
        i++;
    }
    return maximum;
}

int main() {
    int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: " << maximum_adj(arr, size);
    return 0;
}

Đầu ra

Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4