TÌM MẢNG CON CÓ TỔNG LỚN NHẤT

  -  

Ví dụ: cho 1 hàng số <−2, 1, −3, 4, −1, 2, 1, −5, 4>, dãy bé thường xuyên bao gồm tổnglớn nhất là <4, -1, 2, 1> với tổng là 6.

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

Tuỳ vào cụ thể từng bí quyết cài đặt, bạn cũng có thể có độ tinh vi thuật tân oán là (O(n^3)), (O(n^2)) hay (O(n)).Dưới đây là bí quyết cài đặt thuật toán thù cùng với độ phức hợp là (O(n^3)). Với i là thành phần đầu tiên của hàng nhỏ,j là bộ phận sau cùng của dãy con, k được lặp để tính tổng của dãy bé và so sánh với bestđể mang giá trị lớn nhất.

Xem thêm: Tài Liệu Đề Cương Môn Tiếng Việt Thực Hành (Đại Học Thể Dục Thể Thao Đà Nẵng)

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 có thể cải thiện thuật toán để sở hữu được độ phức hợp là (O(n^2)). Bằng cách đào thải vòng lặp k,cùng tính tân oán tổng tức thì trong khoảng lặp j nlỗi sau.

Xem thêm: Sửa Lỗi Máy Tính Có Mạng Nhưng Không Vào Được Mạng? Chuyện Nhỏ!

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); Để rất có thể bớt độ phức tạp tính toán thù xuống (O(n)), bọn họ thuộc mày mò thuật toán thù Kadane’s algorithm.Tư tưởng của thật tân oán là chia bài xích toán thành bài xích toán thù bé dại rộng, bằng cách tra cứu hàng nhỏ tất cả tổng lớn nhất kết thúctại địa điểm k trong hàng. Lúc kia sẽ có được hai trường vừa lòng xảy ra:

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

Thuật toán được thiết lập nlỗi 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 cài đặt cụ thể, tương tự như lưu giữ thông báo chỉ số của dãy con có tổng lớn nhất được biểu hiện dưới đây. Quý khách hàng gọi cóthể ttê mê 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 " to " best_end " ";int main() findSubArrayMax(); findSubArrayMaxWithIndices();Kết trái khi chạy chương trình bên trên vẫn nlỗi sau: