Dãy con trăn tối đa

Dãy con chung dài nhất (LCS) được định nghĩa là dãy con dài nhất chung cho tất cả các dãy đã cho, với điều kiện là các phần tử của dãy con không bắt buộc phải chiếm các vị trí liên tiếp trong các dãy ban đầu

Nếu S1 và S2 là hai dãy đã cho thì Z là dãy con chung của S1 và S2 nếu Z là dãy con của cả S1 và S2. Hơn nữa, Z phải là một dãy tăng nghiêm ngặt của các chỉ số của cả S1 và S2

Trong một dãy nghiêm ngặt tăng dần, chỉ số của các phần tử được chọn từ dãy ban đầu phải theo thứ tự tăng dần trong Z

Nếu

S1 = {B, C, D, A, A, C, D}

Khi đó, {A, D, B} không thể là dãy con của S1 vì thứ tự các phần tử không giống nhau (nghĩa là. dãy tăng không nghiêm ngặt)

---

Hãy để chúng tôi hiểu LCS với một ví dụ

Nếu

S1 = {B, C, D, A, A, C, D}
S2 = {A, C, D, B, A, C}

Khi đó, các dãy con chung là {B, C}, {C, D, A, C}, {D, A, C}, {A, A, C}, {A, C}, {C, D}, ...

Trong số các dãy con này,

S1 = {B, C, D, A, A, C, D}
S2 = {A, C, D, B, A, C}

0 là dãy con chung dài nhất. Chúng ta sẽ tìm dãy con chung dài nhất này bằng quy hoạch động

Trước khi tiếp tục, nếu bạn chưa biết về lập trình động, vui lòng xem qua lập trình động

---

Sử dụng Lập trình động để tìm LCS

Hãy để chúng tôi lấy hai trình tự

Dãy thứ nhấtDãy thứ hai

Các bước sau đây được thực hiện để tìm dãy con chung dài nhất

1. Tạo bảng có kích thước

   S1 = {B, C, D, A, A, C, D}
   S2 = {A, C, D, B, A, C}

   1 trong đó n và m lần lượt là độ dài của X và Y. Hàng đầu tiên và cột đầu tiên được điền bằng số không.
   
   Khởi tạo bảng
2. Điền vào từng ô của bảng bằng cách sử dụng logic sau
3. Nếu ký tự tương ứng với hàng và cột hiện tại khớp nhau, thì hãy điền vào ô hiện tại bằng cách thêm một ký tự vào phần tử đường chéo. Chỉ một mũi tên vào ô chéo
4. Khác, lấy giá trị lớn nhất từ ​​phần tử cột và hàng trước đó để điền vào ô hiện tại. Trỏ mũi tên vào ô có giá trị lớn nhất. Nếu chúng bằng nhau, chỉ vào bất kỳ trong số chúng.
   
   Điền giá trị
5. Bước 2 được lặp lại cho đến khi đầy bảng.
   
   Điền tất cả các giá trị
6. Giá trị ở hàng cuối cùng và cột cuối cùng là độ dài của dãy con chung dài nhất.
   
   Góc dưới cùng bên phải là chiều dài của LCS
7. Để tìm dãy con chung dài nhất, hãy bắt đầu từ phần tử cuối cùng và đi theo hướng mũi tên. Các phần tử tương ứng với ký hiệu () tạo thành dãy con chung dài nhất.
   
   Tạo đường dẫn theo mũi tên

Do đó, dãy con chung dài nhất là CA

LCS

---

Làm thế nào là một thuật toán lập trình động hiệu quả hơn thuật toán đệ quy trong khi giải quyết vấn đề LCS?

Phương pháp lập trình động giảm số lần gọi hàm. Nó lưu trữ kết quả của mỗi lần gọi hàm để có thể sử dụng nó trong các lần gọi sau mà không cần gọi dự phòng

Trong thuật toán động ở trên, kết quả thu được từ mỗi lần so sánh giữa các phần tử của X và các phần tử của Y được lưu trữ trong một bảng để chúng có thể được sử dụng trong các tính toán sau này

Vì vậy, thời gian thực hiện theo phương pháp động là thời gian thực hiện để lấp đầy bảng (tức là. Ô(mn)). Trong khi đó, thuật toán đệ quy có độ phức tạp là 2max(m, n)

Viết chương trình Python tìm tổng lớn nhất của một dãy con liền kề từ một dãy số cho trước a1, a2, a3,. một. Dãy con có một phần tử cũng là dãy con liên tục

Đầu vào.
Bạn có thể giả sử rằng 1 ≤ n ≤ 5000 và -100000 ≤ ai ≤ 100000.
Các số đầu vào cách nhau bởi dấu cách.
Nhập 0 để thoát.
Nhập dãy số muốn nhập (0 để thoát). 3
Nhập số.
2
4
6
Tổng lớn nhất của dãy con liền kề đã nói.
12 Nhập số của dãy số muốn nhập (0 để thoát). 0

Giải pháp mẫu

Mã Python

while True:
    print("Input number of sequence of numbers you want to input (0 to exit):")
    n = int(input())
    if n == 0:
        break
    else:
        A = []
        Sum = []
        print("Input numbers:") 
        for i in range(n):
            A.append(int(input()))
        Wa = 0
        for i in range(0,n):
            Wa += A[i]
            Sum.append(Wa)
        for i in range(0 , n):
            for j in range(0 , i):
                Num = Sum[i] - Sum[j]
                Sum.append(Num)
        print("Maximum sum of the said contiguous subsequence:")
        print(max(Sum))

Đầu ra mẫu

Input number of sequence of numbers you want to input (0 to exit):
 3
Input numbers:
 2
 4
 6
Maximum sum of the said contiguous subsequence:
12
Input number of sequence of numbers you want to input (0 to exit):
 0

Sơ đồ

Trình chỉnh sửa mã Python

Có một cách khác để giải quyết giải pháp này?

Trước. Viết chương trình Python kiểm tra xem hai đường thẳng PQ và RS có song song không. Bốn điểm đó là P(x1, y1), Q(x2, y2), R(x3, y3), S(x4, y4).
Tiếp theo. Viết chương trình python kiểm tra chu vi hai đường tròn cắt nhau hay trùng nhau.

Mức độ khó của bài tập này là gì?

Dễ dàng trung bình khó

Kiểm tra kỹ năng Lập trình của bạn với bài kiểm tra của w3resource



Theo dõi chúng tôi trên Facebook và Twitter để cập nhật thông tin mới nhất.

con trăn. Lời khuyên trong ngày

liệt kê

Khi bạn cần thêm bộ đếm vào một lần lặp, liệt kê thường là cách tiếp cận tao nhã nhất. Nó sẽ trả về khả năng lặp lại (giả sử danh sách, bộ dữ liệu, phạm vi, chuỗi hoặc từ điển, v.v. ) với bộ đếm và đối tượng trả về sẽ là một liệt kê