Thuật toán Kadane – Tìm tập hợp con có tổng lớn nhất

1. Giới thiệu:

–  Là thuật toán quy hoạch động có thể tìm ra tập hợp con có tổng lớn nhất từ tập hợp ban đầu một cách nhanh chóng, tốc độ thực hiện O(n).

– Chẳng hạn: A = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84} , nên tập hợp con có tổng hợp nhất là {59, 26, -53, 58, 97}

2. Hiện thực:

Hình 1 – Khai báo tập hợp ban đầu

1

Hình 1

Hình 2 – Định nghĩa hàm tìm tổng lớn nhất

1

Hình 2

Hình 3 – Cải tiến hàm để tìm phần tử đầu tiên và bắt đầu của tập con

1

Hình 3

Như vậy là tôi vừa hướng dẫn bạn cài đặt thuật toán Kadane tìm tập hợp con có tổng lớn nhất với tốc độ nhanh nhất có thể. Chúc các bạn thành công!

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s