Dãy con tăng dài nhất (bản khó)

Xem PDF
Tác giả:
corona
Dạng bài
Điểm: 400 (p) Thời gian: 0.2s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
  • Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

  • Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Example

Test 1

Input 
6
1 2 5 4 6 2
Output 
4

Bình luận


  • 5
    SPyofgame    5:09 a.m. 14 Tháng 6, 2020 ← chỉnh sửa 7

    Spoiler Alert

    Hint 1

    • Thử từng dãy con một

    Kiểm tra xem nếu nó là dãy con tăng dần

    Xuất dãy có độ dài dài max

    Hint 2

    • Gọi mảng \(f[]\) với \(f_i\) là giá trị độ dài tối đa tính tới \(i\) || init \(f_i = 1\)

    Ta duyệt \(\forall j < i\) tìm vị trí \(j\) thỏa \(a_j < a_i\)

    Ta liên tục chọn các vị trí \(j\) có \(f_j\) lớn nhất

    \(result = max(x \in f)\)

    Hint 3

    • Gọi mảng \(b[]\) với \(b_i\) là giá trị nhỏ nhất trong các dãy tăng có độ dài \(i\) || init \(b_i = +oo\)

    Gọi res là giá trị \(max(f_j\) \(|\) \(j \leq i)\) hay độ dài max trong các dãy tăng

    \(\forall i \leq n\), ta chặt nhị phân \(f_i\) = vị trí cận dưới của \(a_i\) trên mảng \(b_{[0, res]}\)

    Sau đó gán \(b_{f_i} = a_i\) là xong

    \(result = max(x \in f) + 1 - p\) với p là số thứ tự vị trí bắt đầu mảng \(b\)

    Hint 4

    • Nếu các bạn muốn lấy mảng LIS

    Gọi mảng \(LIS[]\) là mảng cần tìm

    Duyệt ngược từ vị trí cuối về, nếu \(f_i = res\) thì thêm phần tử vào cuối mảng \(LIS\) rồi giảm res

    Đảo ngược lại mảng \(LIS[]\) sau quá trình trên ta thu được dãy con dài nhất

    Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(n)\) auxiliary space | LIS-problem, DP, Binary_search

    C++
    int lis(const vector<int> a)
{
    int n = a.size();
    vector<int> f(n, 1), b(n, +INF);

    int res = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin();
        maximize(res, f[i]);
        b[f[i]] = a[i];          
    }
    return res + 1;

    /// lay mang LIS
    vector<int> LIS;
    while (n--)
        if (f[n] == res)
            LIS.push_back(a[n]), res--;

    reverse(all(LIS));
    return LIS.size();
}

    Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(n)\) auxiliary space | Online Solving, LIS-problem, DP, Binary_search
    C++
    int main()
{
    int n = readInt();
    vector<int> a, f, b;

    int res = 0;
    for (int i = 0; i < n; ++i) {
        a.push_back(readInt());
        b.push_back(+INF);
        f.push_back(lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin());
        maximize(res, f[i]);
        b[f[i]] = a[i];
    }

    cout << res + 1;
    return 0;
}


    • 2
      cuom1999    5:19 a.m. 14 Tháng 6, 2020 ← đã chỉnh sửa

      Cách lấy mảng lis chưa đúng thì phải. Chẳng hạn 1 2 3 5 4 thì nó sẽ trả về 1 2 5 4


      • 3
        SPyofgame    5:40 a.m. 14 Tháng 6, 2020
        C++
        function lis({1, 2, 3, 5, 4})
    f[]   = 0 1 2 3 3 
    b[]   = 1 2 3 4 1073741824 
    LIS[] = 1 2 3 4 
return <- 4

        Em thấy nó vẫn xuất 1, 2, 3, 4 mà anh nhỉ


        • 2
          cuom1999    6:53 a.m. 14 Tháng 6, 2020

          Ah e đúng rồi. A nhầm

      7 bình luận nữa