Vì thấy khá liên quan đến bài này nên mình xin đóng góp thêm về 1 thuật toán vừa đơn giản lại hiệu quả.

Bạn có thể xem mã giả ở đây

Kadane algorithm

arr[int] <- input
// Base
set cur_arr <- arr[0]     // mảng con hiện tại
set max_arr <- cur_arr // mảng con có tổng lớn nhất
//
For i := 1 -> length(arr)-1 :
      if cur_arr > 0:
             cur_arr <- cur_arr + arr[i]
      else:
             cur_arr <- 0
       max_arr <- max(max_arr, cur_arr)

Thuật toán này tuân theo nguyên tắc:

• 1/ Nếu mảng trước đã âm thì không cần giữ làm gì => đặt cur_arr = giá trị hiện tại
• 2/ Nếu mảng trước không âm => cộng mảng trước với giá trị hiện tại

Điều thú vị ở thuật toán này là với mảng âm vẫn có thể cho ra được đoạn con có tổng lớn nhất!

include

using namespace std; int main() {

int n;
long long ketqua =0;
long ketquatam =0;
cin >> n;
int aray[n];
for (int i=0; i<n; i++)

{

cin >> aray[i];

}

for (int i=0; i<n; i++){
    ketquatam += aray[i];
    if (ketquatam<=0)
        ketquatam = 0;
    if (ketqua<= ketquatam)
    	ketqua = ketquatam;
}
cout << ketqua;
return 0;
}