Gợi ý:

Để giải bài toán này, bạn có thể sử dụng thuật toán Kadane. Thuật toán này sẽ giúp tìm dãy con liên tiếp có tổng lớn nhất trong một dãy số với độ phức tạp thời gian là ~O(N)~, rất phù hợp với giới hạn ~N \leq 10^6~. Đoạn mã bạn đưa ra là phần cốt lõi của Thuật toán Kadane, được dùng để tìm dãy con liên tiếp có tổng lớn nhất trong một mảng số nguyên. Sau đây là phần giải thích chi tiết từng dòng mã của đoạn mã này:

Đoạn mã:

// Thuật toán Kadane
long long max_sum = a[0], current_sum = a[0];
for (int i = 1; i < N; ++i) {
    current_sum = max(a[i], current_sum + a[i]);
    max_sum = max(max_sum, current_sum);
}

Giải thích từng phần:

1. Khởi tạo biến:

   long long max_sum = a[0], current_sum = a[0];
   

   • max_sum: Đây là biến dùng để lưu trữ tổng lớn nhất mà ta đã tìm thấy cho đến thời điểm hiện tại. Ban đầu, giá trị của max_sum là phần tử đầu tiên trong mảng a[0].
   • current_sum: Đây là biến dùng để lưu trữ tổng của dãy con hiện tại (tổng của dãy con kết thúc tại phần tử a[i]). Ban đầu, giá trị của current_sum cũng được khởi tạo bằng a[0].

2. Duyệt qua các phần tử còn lại của mảng (for loop):

   for (int i = 1; i < N; ++i) {
   

   Vòng lặp này bắt đầu từ i = 1 (vì chúng ta đã khởi tạo với phần tử đầu tiên) và duyệt qua tất cả các phần tử còn lại trong mảng từ a[1] đến a[N-1].

3. Cập nhật giá trị của current_sum:

   current_sum = max(a[i], current_sum + a[i]);
   

   • a[i]: Đây là giá trị hiện tại tại chỉ số i trong mảng.
   • current_sum + a[i]: Tổng dãy con nếu ta tiếp tục cộng thêm phần tử a[i] vào dãy con trước đó (dãy con kết thúc tại i-1).

   Điều này có nghĩa là, chúng ta có hai lựa chọn:

   • Lựa chọn 1: Bắt đầu một dãy con mới từ chính phần tử a[i]. Tổng của dãy con này là a[i].
   • Lựa chọn 2: Tiếp tục dãy con cũ và cộng thêm phần tử a[i] vào tổng dãy con hiện tại.

   Lý do sử dụng max: Chúng ta chọn giá trị lớn nhất giữa hai lựa chọn:

   • Nếu dãy con cũ cộng thêm a[i] sẽ mang lại tổng lớn hơn, ta tiếp tục dãy con đó.
   • Nếu bắt đầu một dãy con mới từ a[i] sẽ tốt hơn, ta sẽ khởi tạo lại dãy con từ phần tử đó.

   Kết quả cuối cùng của current_sum là tổng dãy con lớn nhất kết thúc tại chỉ số i.

4. Cập nhật giá trị của max_sum:

   max_sum = max(max_sum, current_sum);
   

   • max_sum: Biến này giữ tổng lớn nhất của tất cả các dãy con mà ta đã duyệt qua cho đến thời điểm hiện tại. Sau mỗi bước, chúng ta cập nhật giá trị max_sum với giá trị lớn nhất giữa max_sum hiện tại và current_sum.
   • Nếu tổng của dãy con hiện tại (current_sum) lớn hơn tổng lớn nhất trước đó (max_sum), ta sẽ cập nhật max_sum bằng current_sum.

// Thuật toán Kadane
long long max_sum = a[0], current_sum = a[0];
for (int i = 1; i < N; ++i) {
    current_sum = max(a[i], current_sum + a[i]);
    max_sum = max(max_sum, current_sum);
}

Ví dụ 1:

Giả sử bạn có mảng sau:
a = [3, -2, 5, -1, 4, -3, 2]

1. Khởi tạo:

   • max_sum = 3, current_sum = 3

2. Duyệt qua các phần tử từ i = 1 đến i = 6:

   • i = 1: current_sum = max(-2, 3 + (-2)) = 1, max_sum = max(3, 1) = 3
   • i = 2: current_sum = max(5, 1 + 5) = 6, max_sum = max(3, 6) = 6
   • i = 3: current_sum = max(-1, 6 + (-1)) = 5, max_sum = max(6, 5) = 6
   • i = 4: current_sum = max(4, 5 + 4) = 9, max_sum = max(6, 9) = 9
   • i = 5: current_sum = max(-3, 9 + (-3)) = 6, max_sum = max(9, 6) = 9
   • i = 6: current_sum = max(2, 6 + 2) = 8, max_sum = max(9, 8) = 9

Kết quả cuối cùng: Tổng lớn nhất của dãy con liên tiếp là 9.

Ví dụ 2:

Giả sử bạn có mảng sau:
a = [-3, -2, 5, -1, 4, -3, 2]

1. Khởi tạo:

   • max_sum = -3, current_sum = -3

2. Duyệt qua các phần tử từ i = 1 đến i = 6:

   • i = 1: current_sum = max(-2, -3 + (-2)) = -2, max_sum = max(-3, -2) = -2
   • i = 2: current_sum = max(5, -2 + 5) = 5, max_sum = max(-2, 5) = 5
   • i = 3: current_sum = max(-1, 5 + (-1)) = 4, max_sum = max(4, 5) = 5
   • i = 4: current_sum = max(4, 4 + 4) = 8, max_sum = max(5, 8) = 8
   • i = 5: current_sum = max(-3, 8 + (-3)) = 5, max_sum = max(8, 5) = 8
   • i = 6: current_sum = max(2, 5 + 2) = 7, max_sum = max(7, 8) = 8

Kết quả cuối cùng: Tổng lớn nhất của dãy con liên tiếp là 8.

Tóm lại:

• current_sum theo dõi tổng dãy con lớn nhất kết thúc tại phần tử hiện tại.
• max_sum lưu tổng lớn nhất của tất cả các dãy con đã duyệt qua.
• Thuật toán Kadane chỉ cần duyệt mảng một lần với thời gian O(N) và rất hiệu quả để giải quyết bài toán tìm dãy con có tổng lớn nhất.

Phân tích độ phức tạp:

• Độ phức tạp thời gian: ~O(N)~ do thuật toán chỉ cần duyệt qua một lần duy nhất dãy số.
• Độ phức tạp bộ nhớ: ~O(N)~ vì chúng ta sử dụng một mảng để lưu trữ dãy số.