Tác giả: admin

Gọi f[i] là dãy con liên tiếp có tổng lớn nhất mà kết thúc tại a_i. Xây dựng công thức đơn giản f[i]=max⁡(f[i-1]+a[i],a[i]). Sau đó xây dựng mảng ff[i]=max⁡{f[1],f[2],…,f[i]}, công thức dễ dàng nhận ra ff[i]=max⁡{ff[i-1],f[i]}. Sau đó chúng ta xây thêm một mảng g[i] là dãy con liên tiếp có tổng lớn nhất mà bắt đầu tại a_i, công thức tương tự như việc xây dựng mảng f đó là g[i]=max⁡(g[i+1]+a[i],a[i]}. Sau đó nhận thấy, do cả hai dãy đều không có phần tử chung nếu giả sử dãy thứ nhất bắt đầu tại vị trí i thì dãy thứ hai phải kết thúc tại vị trí nhỏ hơn i. Do đó ta sẽ duyệt mọi i=2→N sau đó lấy kết quả lớn nhất trong các giá trị (ff[i-1]+g[i]). Như vậy độ phức tạp cỡ O(5N).