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

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

1. Đang khởi tạo max_till_now = 0
2. Đang khởi tạo max_ending = 0
3. Lặp lại các bước từ 4 đến 6 cho mọi phần tử trong mảng
4. Đặt max_ending = max_ending + a[i]
5. nếu [max_ending 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 Kadane

   Dướ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