ANARC05B.cpp

#include <iostream>
using namespace std;

const int MAX = 10005;

int N[2];           // Lưu số chiều dài của 2 dãy
int Seq[2][MAX];    // Lưu thông tin 2 dãy
int Common[2][MAX]; // Lưu id thành phần chung của 2 dãy
int NumCmn;         // Độ dài thành phần chung 2 dãy
int First, Second;  // Dãy ngắn hơn gọi là First, dãy còn lại là Second
int MaxSum[2][MAX]; // Tính giá trị lớn nhất tại mỗi điểm khi đi từ đầu

/*
* Tìm trong mảng a, độ dài leng, phần tử có giá trị k
* RETURN: chỉ số của phần tử k trong mảng nếu tìm thấy, ngược lại là -1
*/
int BinarySearch(int *a, int leng, int k)
{
	int left = 1, right = leng, mid = 0;
	while(left < right)
	{
		mid = (left + right) / 2;
		if(a[mid] == k) return mid;

		if(a[mid] > k) right = mid - 1;
		else left = mid + 1;
	}
	if(a[left] == k) return left;
	return -1;
}

int main(int argc, char** argv)
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N[0];

	while(N[0] != 0)
	{
		// Nhập đầu vào
		for(int i = 1; i <= N[0]; i++)
			cin >> Seq[0][i];
		cin >> N[1];
		for(int i = 1; i <= N[1]; i++)
			cin >> Seq[1][i];

		// Tìm dãy ngắn hơn
		if(N[0] < N[1]) First = 0;
		else First = 1;
		Second = 1 - First;

		// Duyệt dãy ngắn hơn để tìm ra thành phần chung
		NumCmn = 0;
		for(int i = 1; i <= N[First]; i++)
		{
			// Tìm trong dãy hai, vị trí của 1 số có giá trị ở dãy 1 đang xét
			int t = BinarySearch(Seq[Second], N[Second], Seq[First][i]);

			// Nếu tìm thấy
			if(t != -1)
			{
				NumCmn += 1;
				Common[First][NumCmn] = i;
				Common[Second][NumCmn] = t;
			}
		}

		// Tìm giá trị lớn nhất tại mỗi điểm bằng cách đi từ đầu
		MaxSum[First][0] = 0;
		MaxSum[Second][0]= 0;
		for(int c = 1; c <= NumCmn; c++)
		{
			for(int i = Common[First][c-1]; i < Common[First][c]; i++)
				MaxSum[First][i + 1] = MaxSum[First][i] + Seq[First][i + 1];

			for(int i = Common[Second][c-1]; i < Common[Second][c]; i++)
				MaxSum[Second][i + 1] = MaxSum[Second][i] + Seq[Second][i + 1];

			int t = max(MaxSum[First][Common[First][c]], MaxSum[Second][Common[Second][c]]);
			MaxSum[First][Common[First][c]] = MaxSum[Second][Common[Second][c]] = t;
		}

		for(int i = Common[First][NumCmn]; i < N[First]; i++)
			MaxSum[First][i + 1] = MaxSum[First][i] + Seq[First][i + 1];
		for(int i = Common[Second][NumCmn]; i < N[Second]; i++)
			MaxSum[Second][i + 1] = MaxSum[Second][i] + Seq[Second][i + 1];

		// In kết quả
		cout << max(MaxSum[First][N[First]], MaxSum[Second][N[Second]]) << endl; 
		cin >> N[0];
	}
	return 0;//Your program should return 0 on normal termination.
}