Dãy Con Chung Tổng Lớn Nhất

Buổi 22 — DP 2D & LIS Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.
Draft saved