Card Game is Fun
Time limit1sMemory limit128 MB
Anna may delete arbitrary cards from her sequence and Bruno may trim cards from the top and bottom of his; find the longest common subarray obtainable.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Array, Prefix sum, String matching
- Solved
- No attempts yet
Problem
There are many cards, each showing one integer from to . Anna and Bruno play the following game with these cards.
Anna holds a pile of cards and Bruno holds a pile of cards. Anna discards any number of cards (possibly ) from her cards to form a new pile. Bruno discards some number of cards (possibly ) from the top of his pile of cards and some number of cards (possibly ) from the bottom to form a new pile. When discarding, the order of the remaining cards is never changed.
If the two piles formed this way are identical, the number of cards in one of the piles becomes the score of both players. Here, the two piles are identical if they contain the same number of cards and, for every position, the integer on the -th card from the top () is the same in both piles.
For example, suppose Anna holds 5 cards showing from top to bottom, and Bruno holds 4 cards showing from top to bottom. If Anna discards the cards and Bruno discards the top and the bottom , both piles become from the top and are identical. The remaining pile has 2 cards, so both players score .
We want to find the maximum possible score. Given the information about the piles held by Anna and Bruno, write a program that computes the maximum score.
Input
Read the following data from standard input.
- The first line contains two integers and , separated by a space.
- The second line contains integers separated by spaces; the -th integer () is the integer written on the -th card from the top of Anna's pile.
- The third line contains integers separated by spaces; the -th integer () is the integer written on the -th card from the top of Bruno's pile.
Constraints
- Every integer written on a card is between and , inclusive.
Output
Print the maximum score as a single integer on one line.