CareerCup

The below solution may work upto some extent

static int getDNAAlignment(String dna1, String dna2) {
		final int maxn = 110;
		int b[][] = new int[maxn][maxn];
		int[][] a = new int[300][300];
		a['A']['A'] = 5;
		a['A']['C'] = a['C']['A'] = -1;
		a['A']['G'] = a['G']['A'] = -2;
		a['A']['T'] = a['T']['A'] = -1;
		a['A']['-'] = a['-']['A'] = -3;
		a['C']['C'] = 5;
		a['C']['G'] = a['G']['C'] = -3;
		a['C']['T'] = a['T']['C'] = -2;
		a['C']['-'] = a['-']['C'] = -4;
		a['G']['G'] = 5;
		a['G']['T'] = a['T']['G'] = -2;
		a['G']['-'] = a['-']['G'] = -2;
		a['T']['T'] = 5;
		a['T']['-'] = a['-']['T'] = -1;

		int i = dna1.length();
		int j = dna2.length();
		int s;

		for (int k = 0; k <= i; k++) {
			for (int l = 0; l <= j; l++) {
				if (k == 0 && l == 0)
					b[k][l] = 0;
				else if (k == 0)
					b[k][l] = a['-'][dna2.charAt(l - 1)] + b[k][l - 1];
				else if (l == 0)
					b[k][l] = a[dna1.charAt(k - 1)]['-'] + b[k - 1][l];
				else {
					s = a['-'][dna2.charAt(l - 1)] + b[k][l - 1];

					if (s < a[dna1.charAt(k - 1)]['-'] + b[k - 1][l])
						s = a[dna1.charAt(k - 1)]['-'] + b[k - 1][l];
					if (s < a[dna1.charAt(k - 1)][dna2.charAt(l - 1)]
							+ b[k - 1][l - 1])
						s = a[dna1.charAt(k - 1)][dna2.charAt(l - 1)]
								+ b[k - 1][l - 1];
					b[k][l] = s;
				}
			}
		}
		return b[i][j];
	}

The java solution is below.. it may work for 90 percent of the cases

static int getDNAAlignment(String dna1, String dna2) {
		final int maxn = 110;
		int b[][] = new int[maxn][maxn];
		int[][] a = new int[300][300];
		a['A']['A'] = 5;
		a['A']['C'] = a['C']['A'] = -1;
		a['A']['G'] = a['G']['A'] = -2;
		a['A']['T'] = a['T']['A'] = -1;
		a['A']['-'] = a['-']['A'] = -3;
		a['C']['C'] = 5;
		a['C']['G'] = a['G']['C'] = -3;
		a['C']['T'] = a['T']['C'] = -2;
		a['C']['-'] = a['-']['C'] = -4;
		a['G']['G'] = 5;
		a['G']['T'] = a['T']['G'] = -2;
		a['G']['-'] = a['-']['G'] = -2;
		a['T']['T'] = 5;
		a['T']['-'] = a['-']['T'] = -1;

		int i = dna1.length();
		int j = dna2.length();
		int s;

		for (int k = 0; k <= i; k++) {
			for (int l = 0; l <= j; l++) {
				if (k == 0 && l == 0)
					b[k][l] = 0;
				else if (k == 0)
					b[k][l] = a['-'][dna2.charAt(l - 1)] + b[k][l - 1];
				else if (l == 0)
					b[k][l] = a[dna1.charAt(k - 1)]['-'] + b[k - 1][l];
				else {
					s = a['-'][dna2.charAt(l - 1)] + b[k][l - 1];

					if (s < a[dna1.charAt(k - 1)]['-'] + b[k - 1][l])
						s = a[dna1.charAt(k - 1)]['-'] + b[k - 1][l];
					if (s < a[dna1.charAt(k - 1)][dna2.charAt(l - 1)]
							+ b[k - 1][l - 1])
						s = a[dna1.charAt(k - 1)][dna2.charAt(l - 1)]
								+ b[k - 1][l - 1];
					b[k][l] = s;
				}
			}
		}
		return b[i][j];
	}