Thuật toán Kadane

Thuật toán Kadane là thuật toán tốt nhất để tìm mảng con có tổng lớn nhất trong số tất cả các mảng con.

arr[]={-5, 4,  6, -3 , 4, -1}

Trong mảng này, mảng con {4, 6, -3 , 4 } có tổng lớn nhất.

Cách tiếp cận đơn giản nhất để giải quyết vấn đề này là tính tổng của tất cả các mảng con rồi in ra mảng con có tổng lớn nhất. Nhưng vì cách này cần hai lần lặp nên độ phức tạp thời gian là n² . 

Thuật toán Kadane giúp giảm đáng kể độ phức tạp thời gian.

Cách tiếp cận

Khi phần tử của mảng con là số dương, ta có thể cộng phần tử đó vào tổng. 

Vì vậy, nếu tổng tích lũy của một mảng con bất kỳ là số âm thì hãy bỏ qua phần đó. 

Bắt đầu từ đầu mảng và cộng các phần tử, đồng thời lưu tổng tích lũy lớn nhất. Nếu tổng trở thành số âm, hãy bỏ phần đó và bắt đầu lại từ chỉ số tiếp theo.

1. Tạo hai biến maxSum và cumSum, rồi gán cả hai bằng 0.

2. Chạy một vòng lặp từ 0 đến n lần.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
  
}

3. Tính tổng tích lũy của mảng con như sau

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
}

4. Nếu cumSum lớn hơn maxSum thì lưu giá trị đó vào maxSum.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
}

5. Như đã thảo luận, nếu tổng tích lũy trở thành số âm thì hãy bỏ qua phần đó. Vì tổng lớn nhất mà phần đó có thể tạo ra đã được lưu trong biến maxSum. Do đó, nếu cumSum trở thành số âm thì gán lại bằng 0 và bắt đầu lại từ chỉ số tiếp theo như sau

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
   
   if(cumSum<0){
      cumSum=0;
   }
}

6. Sau khi duyệt qua toàn bộ mảng, tổng lớn nhất được lưu trong biến maxSum.

Hãy nhớ rằng nếu tổng lớn nhất của mảng con là số âm thì ta phải sửa đổi hàm cho phù hợp. Hãy tự thử một lần.

Phân tích độ phức tạp thời gian

Vì ta chỉ duyệt qua mảng một lần nên độ phức tạp thời gian là O(n). Đây là cải thiện đáng kể so với cách tiếp cận trước đó.

Để tìm hiểu thêm về thuật toán Kadane

Thuật toán Kadane