// Path: src/main/java/edu/umd/marbl/mhap/align/Alignment.java
// public enum Operation
// {
// 	MATCH,
// 	INSERT,
// 	DELETE;
// }


import edu.umd.marbl.mhap.align.Alignment.Operation;
import java.util.ArrayList;
import java.util.Collections;
		int maxJ = 0;
		for (int i=1; i<=a.length(); i++) {
			for (int j=1; j<=b.length(); j++)
			{			
				P[i][j] = Math.max(D[i-1][j]+this.gapOpen, P[i-1][j]+this.gapExtend);
				Q[i][j] = Math.max(D[i][j-1]+this.gapOpen, Q[i][j-1]+this.gapExtend);
								
				float score = D[i-1][j-1]+(float)a.similarityScore(b, i-1, j-1)+this.scoreOffset;
				
				//compute the actual score
				D[i][j] = Math.max(score, Math.max(P[i][j], Q[i][j]));
				
				if (D[i][j] > maxValue) {
					maxValue = D[i][j];
					maxI = i;
					maxJ = j;
				}
			}
		}
		
		float score = maxValue;
				
		int a1 = 0;
		int a2 = Math.max(0, maxI-1);
		int b1 = 0;
		int b2 = Math.max(0, maxJ-1);

		if (storePath)
		{
			//figure out the path
// Path: src/main/java/edu/umd/marbl/mhap/align/Alignment.java
// public enum Operation
// {
// 	MATCH,
// 	INSERT,
// 	DELETE;
// }


// Path: src/main/java/edu/umd/marbl/mhap/align/Aligner.java
import edu.umd.marbl.mhap.align.Alignment.Operation;
import java.util.ArrayList;
import java.util.Collections;

		int maxJ = 0;
		for (int i=1; i<=a.length(); i++) {
			for (int j=1; j<=b.length(); j++)
			{			
				P[i][j] = Math.max(D[i-1][j]+this.gapOpen, P[i-1][j]+this.gapExtend);
				Q[i][j] = Math.max(D[i][j-1]+this.gapOpen, Q[i][j-1]+this.gapExtend);
								
				float score = D[i-1][j-1]+(float)a.similarityScore(b, i-1, j-1)+this.scoreOffset;
				
				//compute the actual score
				D[i][j] = Math.max(score, Math.max(P[i][j], Q[i][j]));
				
				if (D[i][j] > maxValue) {
					maxValue = D[i][j];
					maxI = i;
					maxJ = j;
				}
			}
		}
		
		float score = maxValue;
				
		int a1 = 0;
		int a2 = Math.max(0, maxI-1);
		int b1 = 0;
		int b2 = Math.max(0, maxJ-1);

		if (storePath)
		{
			//figure out the path
			ArrayList<Alignment.Operation> backOperations = new ArrayList<>(a.length()+b.length());