Tìm đoạn có tổng dương dài nhất

[Nobita004 (Kirito-kun)]

Cho dãy số a1,a2,a3,...,an (n <= 10^6).
Tìm đoạn dài nhất aL,aL+1,..., aH có tổng dương.

Dữ liệu vào:

• Dòng đầu tiên là số n (n<=10^6)
• Dòng tiếp theo là n số a1,a2,...,an cách nhau một dấu cách.

Dữ liệu ra:
Hai số L, H thoả mãn đề bài.

Ví dụ:
INPUT:

10
-5 -2 -3 4 -6 7 -8 9 -1 -20

OUTPUT:

3 9

Với bài này thì với n<=10^5 em làm được rồi nhưng với 10^6 thì chưa được. Mong anh chị chỉ giúp em thuật toán để vượt qua với ạ. Độ phức tạp là O(n). Em cảm ơn!

[Bui_Hoat (Bùi Hoạt)]

Bài này làm cây BIT bạn nhé. ĐPT: N*log2(N). Chắc chắn qua. Nhưng phải kết hợp với rời rạc hóa bằng cách chặt nhị phân bạn nhé

[rogp10]

1. Tính suffix sum S[1…n]
2. Bài toán đưa về tìm i - j max sao cho S[i] > S[j] (và i > j)
   Dạng này ta dùng hai mảng scan max-min ngược chiều nhau.

Time: 3n + 2*O(n)^[1] lần đọc mem, 3n lần ghi mem
Space: 3n + O(1) slot mem (cấp phát 16n bytes)

[1] nếu ghi best - worst thì nó ra 3n - 5n nhưng lại mất đi phần 2 nhân.