TopCoder SRM594: AstronomicalRecords

public class AstronomicalRecords {
    int LCS(long[] A, long[] B) {
        int n = A.Length;
        int m = B.Length;
        var dp = new int[n + 1, m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A[i] == B[j]) {
                    dp[i + 1, j + 1] = Math.Max(dp[i + 1, j + 1], dp[i, j] + 1);
                }
                dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j]);
                dp[i, j + 1] = Math.Max(dp[i, j + 1], dp[i, j]);
            }
        }
        return dp.Cast<int>().Max();
    }

    public int minimalPlanets(int[] A, int[] B) {
        return (
            from a in A
            from b in B
            select
                A.Length + B.Length - LCS(A.Select(x => 1L * x * b).ToArray(), B.Select(x => 1L * x * a).ToArray())
        ).Min();
    }
}