Tối đa subarray brute force Python
|
Trong bài viết này, chúng ta sẽ tìm hiểu thuật toán kadane là gì và tính chất giải bài toán của nó để giải bài toán “Tổng phân đoạn lớn nhất”. Chúng ta sẽ xem qua thuật toán và mã python cùng với ví dụ và đầu ra tương ứng của nó. Cuối cùng, chúng ta sẽ nghiên cứu độ phức tạp về thời gian của thuật toán và ứng dụng thực tế của thuật toán kadane. Vậy hãy bắt đầu Show Thuật toán của Kadane là gì?Thuật toán Kadane là một trong những cách tiếp cận nổi tiếng để giải bài toán bằng quy hoạch động. Như chúng ta đã biết, bài toán cực đại mảng con là một trong những bài toán nổi tiếng trong lĩnh vực quy hoạch động. Chắc hẳn bạn đang nghĩ bài toán có vẻ dễ và kết quả của bài toán sẽ là tổng của tất cả các phần tử trong một mảng. Nhưng điều này là không chính xác. Trong mảng sẽ có các phần tử nguyên âm có thể làm giảm tổng của cả mảng. Do đó, để giải quyết vấn đề này, chúng ta sẽ sử dụng thuật toán kadane Ở đây thuật toán sẽ tìm mảng con liên tục trong mảng số nguyên 1D có tổng lớn nhất có thể. Cách tiếp cận đầu tiên cho mọi người sau khi hiểu được tuyên bố vấn đề sẽ là áp dụng cách tiếp cận vũ phu và giải quyết vấn đề. Nhưng làm như vậy, độ phức tạp thời gian của giải pháp sẽ là O(n2), điều này không tốt lắm. Do đó, chúng tôi sẽ áp dụng thuật toán của kadane để giải quyết vấn đề bằng cách duyệt qua toàn bộ mảng bằng hai biến để theo dõi tổng cho đến nay và tổng tối đa. Điều quan trọng nhất cần chú ý khi sử dụng thuật toán này là điều kiện sử dụng mà chúng tôi sẽ cập nhật cả hai biến Thuật toán cho Tổng phân đoạn tối đa
Trong thuật toán trên, max_ending được sử dụng để tìm tất cả các phần tử dương của mảng và max_till_now được sử dụng để tìm tổng các phần tử lớn nhất trong số tất cả các phân đoạn dương. Do đó, mỗi lần chúng tôi nhận được tổng dương trong khi so sánh với max_till_now, chúng tôi sẽ cập nhật nó với tổng lớn hơn Do đó, khi max_ending trở thành âm, chúng tôi đặt nó thành 0 và ở mỗi lần lặp lại, chúng tôi kiểm tra max_till_now < max_ending để cập nhật max_till_now nếu điều kiện trả về đúng Thí dụXét mảng số nguyên sau
Đang khởi tạo max_till_now = 0 và max_ending = 0 (i = 0)
Bây giờ, với i = 1, chúng tôi nhận được max_till_now = 0 và max_ending = 0 nhưng với i = 2 max_till_now = 4 và max_ending = 4
Bây giờ i = 3, i = 4, chúng ta lần lượt có max_till_now = 4 và max_ending = 3, max_till_now = 4 và max_ending = 1
Bây giờ, khi i = 5, chúng tôi nhận được max_till_now = 6 (6>4) và max_ending = 6
Và khi i = 6, chúng ta nhận được max_till_now = 6 và max_ending = 3 Do đó, từ ví dụ trên, ta tìm được mảng con lớn nhất là từ i = 2 đến i = 5 và tổng lớn nhất là 6 Mã Python cho thuật toán của KadaneDưới đây là mã python cho thuật toán của kadane def maxSubArraySum(arr,size): max_till_now = arr[0] max_ending = 0 for i in range(0, size): max_ending = max_ending + arr[i] if max_ending < 0: max_ending = 0 elif (max_till_now < max_ending): max_till_now = max_ending return max_till_now arr = [-2, -3, 4, -1, -2, 5, -3] print("Maximum Sub Array Sum Is" , maxSubArraySum(arr,len(arr))) đầu raĐầu ra của đoạn mã trên sẽ như dưới đây Tổng mảng phụ tối đa là 6 Thời gian phức tạpĐộ phức tạp về thời gian của thuật toán kadane cho một mảng chứa n phần tử nguyên là O(n) vì chỉ có một vòng lặp for được thực hiện trong suốt chương trình. Tương tự, độ phức tạp không gian phụ của thuật toán là O(1) Các ứng dụngCó rất nhiều ứng dụng của thuật toán kadane và một số trong số chúng được đề cập dưới đây
Phần kết luậnDo đó, từ phát biểu bài toán tìm tổng mảng con lớn nhất, giải pháp có vẻ không dễ dàng như vậy nhưng bằng cách sử dụng thuật toán của kadane, chúng tôi đã đơn giản hóa nó và đạt được giải pháp với độ phức tạp về thời gian ít nhất. Điều này có thể thực hiện được vì thuật toán của kadane sử dụng kỹ thuật thu thập thông tin cần thiết để đạt được giải pháp tránh lưu trữ dữ liệu không cần thiết và do đó, thuật toán này có thể được coi là một ví dụ đơn giản về phương pháp lập trình động với nhiều ứng dụng thực tế trong thực tế. . |
