Khoảng tải lớn nhất trong bộ đệm động

Bối cảnh

Một thiết bị ghi n mức tải liên tiếp vào một buffer có kích thước chỉ biết khi chạy chương trình, vì vậy dữ liệu phải được cấp phát bằng new[]. Giá trị có thể dương hoặc âm: số dương biểu diễn phần tải tăng thêm, số âm biểu diễn phần tải giảm. Kỹ sư muốn tìm một đoạn liên tiếp có tổng lớn nhất để xác định khoảng thời gian hệ thống chịu tải cao nhất.

Nếu có nhiều đoạn có cùng tổng tối đa, chọn đoạn ngắn hơn; nếu vẫn hòa, chọn đoạn có chỉ số bắt đầu nhỏ hơn. Bài toán yêu cầu duyệt mảng thông qua pointer hoặc pointer arithmetic để gắn đúng với B19. Không được copy sang vector rồi bỏ qua lifetime của raw array. Điểm khó của Homework Medium nằm ở việc duy trì state currentSum/currentStart và đồng thời áp dụng tie-break cho đáp án toàn cục, trong khi cuối chương trình vẫn phải giải phóng đúng vùng nhớ bằng delete[].

Yêu cầu

1. Đọc n và cấp phát long long* a = new long long[n].
2. Duyệt dữ liệu qua pointer để tìm đoạn liên tiếp có tổng lớn nhất.
3. Tie: tổng lớn nhất → độ dài nhỏ hơn → L nhỏ hơn.
4. In bestSum L R 0-based.
5. Giải phóng bằng delete[].

Yêu cầu tổ chức code

Bắt buộc cấp phát raw dynamic array và cleanup đúng; không chuyển toàn bộ dữ liệu sang vector.

Online Judge chấm output. Giảng viên có thể review source code để kiểm tra việc sử dụng đúng pointer/lifetime/string pipeline theo phạm vi buổi học.

Input

Dòng 1 n. Dòng 2 n số nguyên.

Output

Một dòng bestSum L R.

Ràng buộc

1≤n≤5000, |a[i]|≤10^9.

Ví dụ 1

Input

8
-2 3 5 -1 4 -10 6 1

Output

11 1 4

Giải thích

Đoạn 3,5,-1,4 ở index 1..4 có tổng 11; đoạn đầu có thêm -2 nên chỉ còn 9, còn đoạn cuối 6,1 có tổng 7. Vì 11 là lớn nhất, đáp án là 11 1 4. Trong quá trình duyệt, current sum được reset khi bắt đầu mới tại một phần tử có lợi hơn việc kéo dài đoạn cũ.

Ví dụ 2

Input

5
-5 -2 -7 -1 -3

Output

-1 3 3

Giải thích

Tất cả giá trị đều âm. Thuật toán không được trả đoạn rỗng có tổng 0; nó phải chọn ít nhất một phần tử. Giá trị lớn nhất là -1 tại index 3, nên đoạn tối ưu là một phần tử [-1], output -1 3 3.

Thông tin học tập

• Module: M06
• Buổi: B19
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: raw dynamic array, pointer traversal, maximum subarray, running state, tie-break
• Giới hạn kiến thức: B01-B19
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100