Khung Giờ Vàng Doanh Thu Công Ty Du Lịch

Mô tả

Chị Hạnh quản lý một công ty du lịch nhỏ trên phố cổ Hội An. Mỗi ngày, chị ghi lại doanh thu (đơn vị: nghìn đồng) theo từng khung giờ liên tiếp từ sáng đến tối. Có khung giờ đoàn khách đổ về ầm ầm, doanh thu dương; có khung giờ vắng khách, chị vẫn phải trả tiền thuê mặt bằng và điện nước, nên doanh thu mang dấu âm.

Chị Hạnh muốn tìm một khung giờ liên tiếp trong ngày sao cho tổng doanh thu lớn nhất, gọi đó là khung giờ vàng. Khung này có thể chỉ gồm một khung giờ duy nhất nếu đó là lúc duy nhất có lãi. Nếu cả ngày ảm đạm, chị sẽ chọn khung giờ ít lỗ nhất (tức là phần tử âm có giá trị tuyệt đối nhỏ nhất).

Nhiệm vụ của bạn: cho danh sách doanh thu theo từng khung giờ, hãy trả về tổng doanh thu của khung giờ vàng.

Đầu vào

• Một mảng số nguyên doanhThu gồm n phần tử, mỗi phần tử là doanh thu của một khung giờ (tính bằng nghìn đồng, có thể âm, dương hoặc bằng không).

Đầu ra

• Trả về một số nguyên duy nhất là tổng doanh thu lớn nhất của một khung giờ liên tiếp.

Ràng buộc

• $1 \le n \le 10^5$
• $-10^6 \le \text{doanhThu}[i] \le 10^6$
• Tổng các phần tử trong một khung giờ liên tiếp bất kỳ luôn nằm trong khoảng $[-10^9, 10^9]$.

Ví dụ

Ví dụ 1:

Đầu vào: [3, -1, 4, -1, 5, -9, 2, 6]

Giải thích từng bước:

• Xét khung giờ từ vị trí 0 đến vị trí 4: $3 + (-1) + 4 + (-1) + 5 = 10$.
• Các khung giờ khác đều cho tổng nhỏ hơn (ví dụ khung chỉ gồm vị trí 7 là 6, khung từ 6 đến 7 là $2 + 6 = 8$).

Đầu ra: 10

Ví dụ 2:

Đầu vào: [-3, -1, -4, -1, -5]

Giải thích: Cả ngày không có khung giờ nào dương. Chọn khung giờ gồm duy nhất vị trí 1 (doanh thu $-1$), đây là giá trị lớn nhất trong toàn mảng.

Đầu ra: -1