DAYSO10 - Hai dãy con
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Cho dãy số gồm n số nguyên a1, a2, …, an. Một đoạn con của dãy được định nghĩa là dãy ai, ai+1, …, aj với 1 ≤ i ≤ j ≤ n, đoạn con này có chiều dài là (j - i + 1). Bây giờ ta chọn hai đoạn con X và Y không có phần tử chung và có cùng chiều dài là k (k >0). Ký hiệu hai đoạn đó là x1, x2, ..., xk và y1, y2, ..., yk. Sau đó tính tổng:

S = x1*yk + x2*yk-1 + ... + xk-1*y2 + xk*y1

Yêu cầu: Với các đoạn con X, Y có thể có trong dãy n số trên, hãy tìm giá trị lớn nhất của S.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (2 ≤ n ≤ 3000).

- Dòng thứ hai là n số nguyên a1, a2, …, an (|ai| ≤ 106), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là giá trị lớn nhất của S.

Ví dụ

  • input
    8
    2 3 0 3 0 3 2 1
    output
    13
  • input
    5
    3 2 -9 1 -8
    output
    72

Test 1: X = { 2, 3 }, Y = { 3, 2 }

Test 2: X = { -8 }, Y = { -9 }

Back to Top