Đang tải…
Đang tải…
Tổng lớn nhất của một dãy con liên tiếp, trong một lượt: khi tổng đang chạy hóa âm thì bỏ nó và bắt đầu lại.
Bắt đầu với riêng phần tử đầu: tổng hiện tại -2, tốt nhất tới giờ -2. Chưa so sánh gì cả — Kadane không bao giờ nhìn lại quá một bước.
1int maxSubarray(int[] a) {2 int best = a[0], cur = a[0];3 for (int i = 1; i < a.length; i++) {4 if (cur < 0) cur = 0; // một tiền tố âm không bao giờ giúp được — bỏ nó5 cur += a[i];6 best = Math.max(best, cur);7 }8 return best;9}