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

Xem PDF

Điểm: 1400 (p) Thời gian: 1.0s 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], ... A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\)\(A[i_1] < A[i_2] < .. < 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ử.

Dữ liệu vào

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

Kết quả

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

Test 1

Input
6
1 2 5 4 6 2
Output
4

Nguồn: vn.spoj


Bình luận


  • 2
    cuom1999 1:39 a.m. 15 Tháng 7, 2020

    Đã update test (credit: A519LeVanDuc)


    • 5
      SPyofgame 5:24 a.m. 14 Tháng 6, 2020

      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\)\(f_j\) lớn nhất

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


      Hint 3

      • 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


      Hint 4

      Sử dụng chặt nhị phân với mảng \(b[]\)\(b_i\) là giá trị nhỏ nhất các dãy \(LIS\) độ dài \(i\)


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

      C++
      int lis(const vector<int> a)
      {
          int n = a.size();
          vector<int> f(n, 1);
      
          for (int i = 0; i < n; ++i)
              for (int j = 0; j < i; ++j)
                  if (a[i] > a[j])
                      maximize(f[i], f[j] + 1);
      
          int res = *max_element(f.begin(), f.end());
          return res;
      
          /// 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 ^ 2)\) time | \(O(n)\) auxiliary space | Online solving, LIS-problem, DP

      C++
      int main()
      {
          int n = readInt();
          vector<int> a, f;
      
          int res = 1;
          for (int i = 0; i < n; ++i) {
              a.push_back(readInt());
              f.push_back(1);
      
              for (int j = 0; j < i; ++j)
                  if (a[i] > a[j])
                      maximize(f[i], f[j] + 1),
                      maximize(res, f[i]);
          }
      
          cout << res;
          return 0;
      }
      
      1 phản hồi