Dãy Con Chung Tổng Lớn Nhất
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho hai dãy số nguyên dương $A$ gồm $N$ phần tử và $B$ gồm $M$ phần tử. Hãy tìm một dãy con chung (không nhất thiết liên tiếp) của $A$ và $B$ sao cho tổng các phần tử của dãy con chung đó là lớn nhất.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$.
- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
- Dòng thứ ba chứa $M$ số nguyên $B_1, B_2, \dots, B_M$.
Dữ liệu ra
Một số nguyên duy nhất là tổng lớn nhất của dãy con chung.
Ví dụ
| Input | Output |
|---|---|
| 4 5 3 1 4 2 1 3 4 5 2 |
9 |
Giới hạn
- $1 \le N, M \le 1000$.
- $1 \le A_i, B_j \le 10^9$.
Community Discussion