dãy lồi dài nhất trong một mảng

Question

Giả sử chúng ta đưa ra một mảng đầu vào của số nguyên, làm thế nào để tìm ra dãy con lồi dài nhất thỏa mãn các điều kiện sau đây:

c[i] < (c[i-1] + c[i+1])/2 

c[i-1], c[i] và c[i+1] ba yếu tố liên tiếp trong sau đó.

Ví dụ: nếu mảng đầu vào là { 1, 2, -1, 0, 3, 8, 5 }, thì con lồi dài nhất sẽ là: { 1, -1, 0, 3, 8 } hoặc { 2, -1, 0, 3, 8 }.

Tôi đã cố gắng giải quyết vấn đề này bằng cách sử dụng cùng ý tưởng lập trình động trong bài toán "Hậu quả gia tăng dài nhất" (LIS). Nhưng vì mỗi phần tử trong chuỗi phụ thuộc vào hai phần tử trước, có vẻ như một giải pháp O (n^2) là không thể. Cảm ơn sự giúp đỡ của bạn.

Answer 1

Đây là O (N log N) Thuật toán (và kể từ log N là ở đây chỉ vì sắp xếp chúng ta có thể giảm xuống còn O (N log log N) hoặc thậm chí đến O (N ) với các thuật toán sắp xếp khác nhau hoặc hàng đợi ưu tiên nâng cao hơn):

1. Tạo mảng cho mỗi cặp thành phần mảng đầu vào: P[]. Các phần tử bên trong mỗi cặp được sắp xếp theo chỉ mục của chúng.
2. Sắp xếp các cặp này theo chênh lệch giá trị Y2 - Y1. Trong trường hợp bằng Y2 - Y1 giá trị, chúng phải được sắp xếp theo chỉ số thứ hai theo thứ tự giảm dần.
3. Mảng không khởi tạo L[] độ dài chuỗi cho các chuỗi kết thúc tại chỉ mục 0 .. N-1.
4. Đối với mỗi cặp từ P[] (theo thứ tự được sắp xếp): L[X2] = max(L[X2], L[X1] + 1). Trong đó X là chỉ mục của phần tử trong mảng đầu vào.
5. Tìm giá trị lớn nhất trong L[]. Đây là chiều dài của con lồi dài nhất.
6. Để có thể tái tạo lại chính bản thân, bướC# 4 cũng nên cập nhật chuỗi các con trỏ ngược. Khi L[X2] được cập nhật, chúng tôi sẽ tạo một nút trỏ đến nút được trỏ theo mục nhập tương ứng với X1, sau đó nhập mục tương ứng với X2 vào nút mới này: BP_Head[X2] = new Node(BP_Head[X1]).

Thuộc tính lồi c[i] < (c[i-1] + c[i+1])/2 có thể được chuyển thành bất bình đẳng tương đương c[i] - c[i-1] < c[i+1] - c[i]. Điều đó có nghĩa là trong khi xử lý các cặp theo thứ tự sắp xếp, chúng ta không cần kiểm tra thuộc tính lồi nữa. Vì vậy, nhiệm vụ duy nhất của bướC# 4 là phát triển các chất nền.

Biến thể đơn giản này của thuật toán cần không gian O (N). Độ phức tạp của không gian có thể bị giảm nếu thay vì một mảng lớn P[], chúng tôi sử dụng bản sao được sắp xếp trước của mảng đầu vào S[] cùng với hàng đợi ưu tiên. BướC# 4 nhận các phần tử từ đầu hàng đợi ưu tiên này. Để giữ kích thước của hàng đợi ưu tiên này bằng N, chúng tôi có thể đẩy phần tử S[i+1] - S[j] vào hàng đợi chỉ sau khi S[i] - S[j] bị xóa (do đó hàng đợi chỉ giữ một phần tử cho mỗi j).Không gian lớn được tiêu thụ bởi forest back-pointers là không cần thiết nếu chúng ta sử dụng một thủ thuật DP đã biết để lưu trữ chỉ một back-pointer (cho mỗi index) trỏ tới "middle" của chuỗi back-pointer ban đầu (và sau đó lặp lại thuật toán này đệ quy cho hai mảng con trước và sau con trỏ sau "ở giữa" này.

---

Và O (N) thuật toán:

1. graph Construct nơi mà mỗi đỉnh tương ứng với (lệnh của chỉ số) cặp phần tử mảng.
2. Kết nối các đỉnh với cạnh nếu chúng có một phần tử mảng chung nằm giữa hai phần tử còn lại được liên kết với các đỉnh này và cả ba phần tử đều thỏa mãn thuộc tính lồi. Cạnh này nên được chuyển đến đỉnh với các chỉ số lớn hơn.
3. Thêm nút nguồn và đích và kết nối chúng với mọi đỉnh.
4. Tìm đường đi dài nhất trong biểu đồ này.

Biểu đồ này có O (N) các đỉnh và O (N) cạnh. Nó có thể được xây dựng trong thời gian O (N); và vì nó là một DAG, việc tìm đường dài nhất cũng mất thời gian O (N).

Answer 2

Cho phép gọi trình tự lồi dài nhất là LCS; Độ dài tối thiểu có thể cho N> 1 là 2. Bản ngã dưới đây là tự giải thích.

int LCS[N]; 
LCS[0] = 1; LCS[1] =2 ; 

for(i=2;i<N;i++) 
{ 
    LCS[i] = 2; 
    for(j=1;j<i;j++) 
    { 
     for(k=0;k<j;k++) 
     { 
      if(LCS[j]-1 == LCS[k] && A[j] < (A[k] + A[i])/2) 
       LCS[i] = max(LCS[i], 1+LCS[j]); 
     } 
    } 
}