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

     

Ví dụ: cho một dãy số <−2, 1, −3, 4, −1, 2, 1, −5, 4>, dãy con liên tiếp có tổnglớn nhất là <4, -1, 2, 1> 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 từng cách cài đặt, chúng ta có thể có độ phức tạp thuật toán là \(O(n^3)\), \(O(n^2)\) hay \(O(n)\).Dưới đây là cách cài đặt thuật toán với độ phức tạp là \(O(n^3)\). Với i là phần tử đầu tiên của dãy con,j là phần tử cuối cùng của dãy con, k được lặp để tính tổng của dãy con và so sánh với bestđể lấy giá trị 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 có thể cải thiện thuật toán để có được độ phức tạp là \(O(n^2)\). Bằng cách loại bỏ vòng lặp k,và tính toán tổng ngay trong vòng lặp j như sau.

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); }}Để có thể giảm độ phức tạp tính toán xuống \(O(n)\), chúng ta cùng tìm hiểu thuật toán Kadane’s algorithm.Tư tưởng của thật toán là chia bài toán thành bài toán nhỏ hơn, bằng cách tìm dãy con có tổng lớn nhất kết thúctại vị trí k trong dãy. Khi đó sẽ có hai trường hợp xảy ra:

Dãy con chỉ chứa phần thử thứ k. So sánh best với phần tử thứ k để cập nhật giá trị lớn nhất. Dãy con chứa phần tử thứ k và dãy con kết thúc ở phần thử thứ k - 1. Cập nhật tổng mới dựa trên tổngcủa dãy con k - 1 và cộng thêm phần tử thứ k. So sánh tổng mới với best để cập nhật giá trị lớn nhất.

Thuật toán được cài đặt 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 "\n";Cách cài đặt chi tiết, cũng như lưu thông tin chỉ số của dãy con có tổng lớn nhất được mô tả 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 "\n";}void findSubArrayMaxWithIndices() { int best = INT_MIN, sum = 0; int best_start = 0, best_end = 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_end = i; } } cout best "\n"; cout "start from " best_start " to " best_end "\n";}int main() { findSubArrayMax(); findSubArrayMaxWithIndices();}Kết quả khi chạy chương trình trên sẽ như sau:


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