Trọng số khoản (Hard ver.)
Xem PDF
Điểm:
500 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Định nghĩa trọng số của một nhóm số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong nhóm đó. (Nhóm có thể có 1 phần tử)
Ví dụ trọng số của nhóm \((3,1,7,2)\) là \(6\), trọng số của nhóm \((40,40)\) là \(0\), trọng số của nhóm \((1208)\) là \(0\).
Cho 1 dãy gồm \(n\) phần tử, phần tử thứ \(i\) có giá trị là \(a_i\).
Yêu cầu:
- Mỗi nhóm là 1 dãy các số liên tiếp.
- Giá trị của dãy số bằng tổng trọng số của tất cả các nhóm. Hãy tìm cách chia sao cho tổng trọng số đạt giá trị lớn nhất.
Input
- Dòng 1: chứa số nguyên \(n (1 \le n \le 10^5)\)
- Dòng 2: chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (-10^9 \le a_i \le 10^9)\)
Output
- Ghi ra giá trị lớn nhất của dãy.
Example
Test 1
Input
6
1 9 6 7 1 6Output
14Note
Dãy số [1 9 6 7 1 6] có thể chia được thành các nhóm: [1 9] | [6 7 1] | [6].
Bình luận
bài này làm kiểu gì vậy ạ
Update: Đã sửa lại test và rejudge toàn bộ bài nộp.