Mô tả và yêu cầu

Cho dãy số gồm n phần tử a1, a2, ..., an.

Tìm giá trị lớn nhất của biểu thức (aj - ai) với (1 <= i < j <= n).

Dữ liệu vào

Dữ liệu vào: seq1.inp

- Dòng đầu nhập số nguyên dương n.
- Dòng thứ 2 nhập n số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: seq1.out

- In ra giá trị lớn nhất của biểu thức.

Giới hạn và chấm điểm

Sub1: n <= 5000.
Sub2: n <= 10^6.

Ví dụ

7
8 2 4 -2 9 1 -3

11

2 số ai, aj là (-2, 9).

Mô tả và yêu cầu

Cho dãy số gồm n phần tử a1, a2, ..., an.

Tìm giá trị lớn nhất của biểu thức (ai + aj - ak) với (1 <= i < j < k <= n).

Dữ liệu vào

Dữ liệu vào: SEQ2.inp

- Dòng đầu nhập số nguyên dương n.
- Dòng thứ 2 nhập n số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ2.out

- In ra giá trị lớn nhất của biểu thức.

Giới hạn và chấm điểm

Sub1: n <= 200.
Sub2: n <= 5000.
Sub3: n <= 10^6.

Ví dụ

7
8 2 4 -5 9 1 -3

20

3 số ai, aj, ak là (8, 9, -3).

Mô tả và yêu cầu

Cho dãy số gồm n phần tử a1, a2, ..., an.

Tìm giá trị lớn nhất của biểu thức (ai + ai+1 + ... + aj) với (1 <= i <= j <= n).

Dữ liệu vào

Dữ liệu vào: SEQ3.inp
- Dòng đầu nhập số nguyên dương n.
- Dòng thứ 2 nhập n số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ3.out
- In ra giá trị lớn nhất của biểu thức.

Giới hạn và chấm điểm

Sub1: n <= 200.
Sub2: n <= 5000.
Sub3: n <= 10^6.

Ví dụ

7
8 -10 6 -5 9 1 -3

11

Dãy con đó là (6, -5, 9, 1).

Mô tả và yêu cầu

Cho dãy gồm số nguyên gồm n phần tử: a1, a2, …, an.

Yêu cầu: tìm dãy con liên tiếp dài nhất có tổng không âm.

Dữ liệu vào

Dữ liệu vào: SEQ4.inp
- Dòng đầu gồm số nguyên dương n.
- n dòng tiếp theo, mỗi dòng chứa một số nguyên ai (1 <= i <= n).

Dữ liệu ra

Kết quả: SEQ4.out
- In ra một kết quả duy nhất là độ dài của dãy con liên tiếp dài nhất có tổng không âm.

Giới hạn và chấm điểm

Sub1: n < 200.
Sub2: n < 5000.
Sub3: n < 10^6.

Ví dụ

7
1
-5
2
-3
-1
4
-1

5

Mô tả và yêu cầu

Cho dãy số gồm n phần tử nguyên dương a1, a2, ..., an và một số nguyên dương k cho trước (k<=10^9).

Tìm dãy con liên tiếp dài nhất có tổng đúng bằng k.

Dữ liệu vào

Dữ liệu vào: SEQ5.inp
- Dòng đầu nhập số nguyên dương n và k.
- Dòng thứ 2 nhập n số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ5.out
- In ra kết quả là độ dài dãy con thỏa mãn yêu cầu.

Giới hạn và chấm điểm

Sub1: n<=200.
Sub2: n<=5000.
Sub3: n<=10^6.

Ví dụ

7 7
4 3 2 1 1 1 6

4

Dãy con đó là: (3, 2, 1, 1)

Mô tả và yêu cầu

Cho dãy số gồm n phần tử a1, a2, ..., an.

Tìm dãy con liên tiếp dài nhất có tính chất FIBONACCI.

Ví dụ: dãy 3 4 7 11 là dãy FIBONACCI nhưng dãy 1 2 3 4 thì không.

Tóm lại, dãy con a_i, a_{i+1}, ..., a_j là dãy FIBONACCI khi mà:

a_i + a_{i+1} = a_{i+2}; a_{i+1} + a_{i+2} = a_{i+3}; ...; a_{j-2} + a_{j-1} = a_j.

Dữ liệu vào

Dữ liệu vào: SEQ6.inp

- Dòng đầu nhập số nguyên dương n.
- Dòng thứ 2 nhập n số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ6.out

- In ra độ dài của dãy con thỏa mãn yêu cầu đề.

Giới hạn và chấm điểm

Sub1: n <= 200.
Sub2: n <= 5000.
Sub3: n <= 10^6.

Ví dụ

7
8 -10 6 -5 1 -4 12

4

Dãy con đó là (6, -5, 1, -4).

Mô tả và yêu cầu

Cho một dãy số nguyên gồm N phần tử a1, a2, ..., an.

Biết rằng dãy con tăng đơn điệu là một dãy ai1, ai2, ..., aik thỏa mãn i1 < i2 < ... < ik và ai1 < ai2 < ... < aik.

Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Dữ liệu vào

Dữ liệu vào: SEQ7.inp

Dòng 1 gồm 1 số nguyên là số N.

Dòng thứ 2 ghi N số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ7.out

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Giới hạn và chấm điểm

1 ≤ ai ≤ 10^9.

Sub1: n < 5000.

Sub2: n <= 500000.

Ví dụ

7
8 -10 6 -5 9 1 12

4

Dãy con đơn điệu độ dài 4 ví dụ là dãy (-10, -5, 1, 12).

Mô tả và yêu cầu

Cho một dãy số nguyên gồm N phần tử a1, a2, ..., an.

Biết rằng dãy con tăng đơn điệu là 1 dãy ai1, ai2, ..., aik thỏa mãn i1 < i2 < ... < ik và ai1 < ai2 < ... < aik. Hãy cho biết số dãy con tăng đơn điệu ít nhất có dãy số gồm n phần tử trên.

VD: dãy (6, 7, 4, 2, 5) thì sẽ có ít nhất 3 dãy con tăng đơn điệu là (6, 7) và (4, 5) và (2).

Dữ liệu vào

Dữ liệu vào: SEQ8.inp

Dòng 1 gồm 1 số nguyên là số N.

Dòng thứ 2 ghi N số nguyên a1, a2, ..., an (1 ≤ ai ≤ 10^9).

Dữ liệu ra

Kết quả: SEQ8.out

In ra kết quả là số dãy con tăng đơn điệu ít nhất.

Giới hạn và chấm điểm

Sub1: n < 5000.
Sub2: n <= 500000.

Ví dụ

7
8 -10 6 -5 9 1 -3

4

Các dãy con tăng là (8); (-10, 6, 9); (-5, 1) và (-3).

Mô tả và yêu cầu

Cho dãy gồm n số nguyên dương và một số nguyên K. Bạn hãy giúp Tèo tìm ra đoạn con dài nhất gồm các phần tử liên tiếp sao cho tổng các phần tử này chia hết cho K.

Dữ liệu vào

Dữ liệu vào: SEQ9.INP
- Dòng 1 là N và K (1<= k <=10^5).
- Dòng thứ 2 là danh sách n phần tử a1, a2, …, an (0<= ai <=10^9).

Dữ liệu ra

Kết quả: SEQ9.OUT
- Là độ dài lớn nhất tìm được.

Giới hạn và chấm điểm

Giới hạn:
- Sub1: n<=5000.
- Sub2: n<=10^6.

Ví dụ

9 4
3 9 9 5 1 1 10 3 5

6

Mô tả và yêu cầu

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 vào

Dữ liệu vào: SEQ10.inp
- Dòng thứ nhất là số nguyên n.
- Dòng thứ hai là n số nguyên a1, a2, …, an (|ai| ≤ 10^6 ), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra

Kết quả: SEQ10.out
- Là giá trị lớn nhất của S.

Giới hạn và chấm điểm

Sub1: 60% số test có n ≤ 50.
Sub2: 40% số test còn lại có n ≤ 3000.

Ví dụ

8
2 3 0 3 0 3 2 1

13

X = { 2, 3 }, Y = { 3, 2 }

Ví dụ 2

5
3 2 -9 1 -8

72

X = { -8 }, Y = { -9 }