Trình tự tăng và giảm theo lượt

Question

Giả sử chúng ta có một chuỗi các số nguyên có độ dài cho trước là n. Chúng tôi muốn xóa một số phần tử (có thể không có), do đó trình tự tăng lên và giảm dần theo kết quả. Nó có nghĩa là, mọi phần tử nên có các phần tử lân cận hoặc lớn hơn cả hai hoặc nhỏ hơn chính nó. Ví dụ: 1 3 2 7 6 và 5 1 4 2 10 cả hai chuỗi đều tăng và giảm theo lượt. Chúng tôi muốn xóa một số yếu tố để biến đổi trình tự của chúng tôi theo cách đó, nhưng chúng tôi cũng muốn tối đa hóa tổng các phần tử còn lại. Vì vậy, ví dụ, từ trình tự 2 18 6 7 8 2 10, chúng tôi muốn xóa 6 và làm cho nó 2 18 7 8 2 10.

Tôi đang tìm giải pháp hiệu quả cho vấn đề đó. Ví dụ trên cho thấy thuật toán tham lam ngây thơ nhất (xóa mọi phần tử đầu tiên phá vỡ trình tự) sẽ không hoạt động - nó sẽ xóa 7 thay vì 6, sẽ không tối đa hóa tổng các phần tử còn lại. Bất kỳ ý tưởng nào để giải quyết hiệu quả (O(n) or O(n log n) có thể) và chính xác?

Answer 1

Đối với mọi phần tử của dãy với chỉ số i chúng tôi sẽ tính toán F(i, high) và F(i, low), nơi F(i, high) tương đương với số tiền lớn nhất của dãy với các đặc tính truy nã kết thúc bằng các yếu tố -thứ i và yếu tố này là một "đỉnh cao" . (Tôi sẽ giải thích chủ yếu phần "cao", phần "thấp" có thể được thực hiện tương tự). Chúng tôi có thể tính toán các chức năng này bằng cách sử dụng các mối quan hệ sau:

Câu trả lời là tối đa trong số tất cả F(i, high) và F(i, low) giá trị.

Điều đó mang lại cho chúng tôi giải pháp lập trình động đơn giản với độ phức tạp thời gian là O(n^2). Nhưng chúng ta có thể đi xa hơn.

Chúng tôi có thể tối ưu hóa phép tính là max(F(j,low)) một phần. Những gì chúng tôi cần làm là tìm giá trị lớn nhất trong số F(j, low) được tính trước đó với điều kiện là a[j] < a[i]. Điều này có thể được thực hiện với segment trees.

Trước hết, chúng tôi sẽ "ép" chuỗi ban đầu của chúng tôi. Chúng ta cần giá trị thực của phần tử a[i] chỉ khi tính tổng. Nhưng chúng tôi chỉ cần thứ tự tương đối của các yếu tố khi kiểm tra rằng a[j] nhỏ hơn a[i]. Vì vậy, chúng tôi sẽ ánh xạ mọi phần tử vào chỉ mục của nó trong mảng các phần tử đã sắp xếp mà không có bản sao. Ví dụ: trình tự a = 2 18 6 7 8 2 10 sẽ được dịch sang b = 0 5 1 2 3 0 4. Điều này có thể được thực hiện trong O(n*log(n)).

Yếu tố lớn nhất của b sẽ nhỏ hơn n, kết quả là chúng tôi có thể tạo cây phân đoạn trên đoạn [0, n] với mỗi nút chứa tổng lớn nhất trong phân khúc (chúng tôi cần hai cây phân đoạn cho "cao" "thấp" một phần cho phù hợp). Bây giờ chúng ta hãy mô tả các bước i của thuật toán:

1. Tìm tổng lớn nhất max_low trên đoạn [0, b[i]-1] sử dụng "thấp" cây phân khúc (ban đầu tất cả các nút của cây chứa zero).
2. F(i, high) bằng max_low + a[i].
3. Tìm số tiền lớn nhất max_high trên đoạn [b[i]+1, n] bằng cách sử dụng cây phân đoạn "cao".
4. F(i, low) bằng max_high + a[i].
5. Cập nhật phân đoạn [b[i], b[i]] của cây phân đoạn "cao" với giá trị F(i, high) tính toán lại giá trị tối đa của các nút chính (và chính là số [b[i], b[i]] nút).
6. Làm tương tự cho cây đoạn "thấp" và F(i, low).

Phân tích phức tạp: b tính toán trình tự là O(n*log(n)). Hoạt động tối đa/cập nhật của phân đoạn có độ phức tạp O(log(n)) và có O(n) trong số đó. Độ phức tạp tổng thể của thuật toán này là O(n*log(n)).