Tìm dãy con có tổng lớn nhất

Ví dụ: cho 1 dãy số <−2, 1, −3, 4, −1, 2, 1, −5, 4>, dãy nhỏ thường xuyên tất cả tổnglớn số 1 là <4, -1, 2, 1> cùng với tổng là 6.

Bạn đang xem: Tìm dãy con có tổng lớn nhất

Tuỳ vào cụ thể từng cách setup, chúng ta có thể tất cả độ phức hợp thuật toán thù là (O(n^3)), (O(n^2)) hay (O(n)).Dưới đó là phương pháp thiết lập thuật toán thù với độ phức tạp là (O(n^3)). Với i là bộ phận đầu tiên của hàng bé,j là phần tử cuối cùng của dãy con, k được lặp để tính tổng của hàng nhỏ với đối chiếu cùng với bestđể mang quý hiếm lớn nhất.

Xem thêm: Mẫu Quy Định Mặc Đồng Phục Công Ty 2021, Quy Định Về Việc Cấp Phát Đồng Phục Công Ty

int best = INT_MIN;for (int i = 0; i n; i ++) for (int j = i; j n; j ++) int sum = 0; for (int k = i; k j; k ++) sum += arr; best = max(best, sum); Chúng ta rất có thể nâng cấp thuật tân oán để sở hữu được độ tinh vi là (O(n^2)). Bằng phương pháp vứt bỏ vòng lặp k,với tính toán thù tổng ngay lập tức trong tầm lặp j nlỗi sau.

Xem thêm: Dap An De Thi Mon Toan Khoi B Nam 2013 Cua Bo Giao Duc Va Dao Tao

int best = INT_MIN;for (int i = 0; i n; i ++) int sum = 0; for (int j = i; j n; j ++) sum += arr; best = max(best, sum); Để hoàn toàn có thể giảm độ tinh vi tính toán thù xuống (O(n)), bọn họ thuộc khám phá thuật toán thù Kadane’s algorithm.Tư tưởng của thiệt tân oán là phân chia bài xích toán thù thành bài toán nhỏ tuổi hơn, bằng cách tìm dãy bé có tổng lớn số 1 kết thúctại địa điểm k vào hàng. lúc đó sẽ có nhì trường vừa lòng xảy ra:

Dãy nhỏ chỉ đựng phần demo máy k. So sánh best cùng với thành phần đồ vật k để cập nhật quý hiếm lớn số 1. Dãy con cất phần tử sản phẩm k và hàng bé kết thúc tại phần test lắp thêm k - 1. Cập nhật tổng bắt đầu dựa trên tổngcủa hàng nhỏ k - 1 với thêm vào đó thành phần đồ vật k. So sánh tổng new cùng với best nhằm cập nhật quý hiếm lớn nhất.

Thuật tân oán được thiết lập như sau:

int best = INT_MIN;int sum = 0;for (int i = 0; i n; i ++) sum = max(arr, sum + arr); best = max(sum, best);cout best " ";Cách thiết đặt chi tiết, tương tự như lưu lại biết tin chỉ số của dãy con tất cả tổng lớn số 1 được mô tả tiếp sau đây. Bạn đọc cóthể tham khảo

#include using namespace std;int n = 9;int arr<9> = -2, 1, -3, 4, -1, 2, 1, -5, 4 ;void findSubArrayMax() int best = INT_MIN, sum = 0; for (int i = 0; i n; i++) sum = max(arr, sum + arr); best = max(best, sum); cout best " ";void findSubArrayMaxWithIndices() int best = INT_MIN, sum = 0; int best_start = 0, best_over = 0, current_start = 0; for (int i = 0; i n; i++) if (sum + arr arr) current_start = i; sum = arr; else sum += arr; if (best sum) best = sum; best_start = current_start; best_kết thúc = i; cout best " "; cout "start from " best_start " lớn " best_end " ";int main() findSubArrayMax(); findSubArrayMaxWithIndices();Kết trái lúc chạy chương trình trên vẫn như sau:


Chuyên mục: Tổng hợp