Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất

This post was flagged by the community and is temporarily hidden.

sort mảng A thành mảng B rồi tìm dãy con chung dài nhất của A và B :V

4 Likes

O(nlogn) :< https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Ý tưởng là ntn:

VD A = [6 1 3 2 5]. Ban đầu ta có dãy con (khác mảng con nhé) 6 độ dài 1.
Xét A[1] = 1 < 6 nên ta thay 1 vào ra 1
Xét A[2] = 3 > 1 nên độ dài 2 là 1, 3
v.v
đáp án là 1, 2, 5

5 Likes

Bác đưa thẳng cái gif này dễ hiểu hơn nè. :slight_smile:

1 Like

Thật sự là mình ko chắc là đã hiểu đúng cái gif này :smiley:

3 Likes

Xem lần đầu chưa hiểu, 2, 3 lần là hiểu ngay thôi. :laughing:

1 Like

Yêu cầu là in ra một dãy mà lấy cái dãy hồi nãy ra là tạch luôn, phải truy vết nữa.

4 Likes

Nhưng mà nhìn vô thì sẽ hình dung được ý tưởng để làm bài này. Nhầm thì cũng khó lắm anh, trừ khi ẩu thôi. :stuck_out_tongue_closed_eyes:

1 Like

Viết lại từ wiki :smiley:

# pseudo
def LIS(a: Array)
   return [] if a.empty?
   trace = [-1].xtend(a.length);
   min_idx_len = [-1, 0].reserve(a.length+1);

   for idx in [1..a.length-1] do
      next if a[idx].nil?
      if a[idx] > a[min_idx_len[-1]]
          trace[idx] = min_idx_len[-1];
          min_idx_len << idx;
      else
          # trả về chỉ số bên trái của đoạn [pivot, a[-1]]
          tmp = min_idx_len.binsearch_range(a[idx], 1, -1, |val| a[val]);
          # trace[idx] lưu chỉ số **ban đầu** ứng với a[idx] 
          trace[idx] = min_idx_len[tmp - 1];
          min_idx_len[tmp] = idx # if a[min_idx_len[tmp]] > a[idx]
      end
   end
  i, idx_outp, min_idx_len[-2] = -1, -2, a[min_idx_len[-1]];
  until trace[i] == -1 do
      i = trace[i];
      min_idx_len[idx_outp-=1] = a[i];
  end
  return min_idx_len.shrink(1)
end

Đầu tiên là phân tích vai trò của min_idx_len[] (cái tên khá củ chuối). Mảng này có thể giãn đến N+1 slot và min_idx_len[i] là chỉ số phần tử cuối cùng của dãy con (sau đây ngầm hiểu là tăng dần) độ dài i.

Ta thấy để trả lời câu hỏi “phần tử này ứng với dãy con độ dài bao nhiêu?” cần tối ưu min_idx_len[], tức là làm sao cho những chỉ số trong mảng ứng với các số bé nhất có thể (*)

Trước hết, ta chứng minh a[min_idx_len[]] phải là mảng tăng ngặt. Do dãy con dài có phần đầu là dãy ngắn hơn, và tính chất (*) nến số ứng với slot cao hơn sẽ phải lớn hơn số ứng với slot thấp hơn.

Như vậy là xong một nửa yêu cầu. Về phần truy vết thì từ một phần tử phải tìm về được phần tử ngay đằng trước nó trong dãy con và ta có ngay min_idx_len[]

5 Likes

Bài LIS này nhiều cách giải và tài liệu tiếng Việt cũng viết khá chi tiết mà bạn!
Cách cơ bản là gọi F[i] là độ dài của LIS bắt đầu hoặc kết thúc tại a[i]. Duyệt i, tìm j sao cho nối được a[i] vào LIS bắt đầu hoặc kết thúc tại a[j] và lấy kết quả lớn nhất. ĐPT là O(n^2).
Giảm xuống O(nlogn) cũng có nhiều cách, có thể dùng biến thể của thuật patience sorting, dùng ctdl segment tree hoặc đơn giản là chặt nhị phân. Nhận xét 1 LIS có 2 tính chất quan trọng là phần tử bắt đầu của LIS và độ dài LIS. Vì dãy không có tính tăng hoặc giảm nên không thao tác với phần tử đầu của LIS được, ta chặt độ dài của LIS.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?