fmemo

fmfm.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.lang.*;

public class DSAP2 {

	// public class res {
	// 	public List tree = new ArrayList();
	// }

	static int fcall = 0;
	static int[][] mem;
	static int[][] arr;
	static int m = 0;


	public static void main(String[] args) {

		//read txt file
		BufferedReader br = null;

		
		try {

			int n = 0;

			//read in file
			String sCurrentLine;
			String file_path = args[1];

			br = new BufferedReader(new FileReader(file_path));
			String nm[] = br.readLine().split(" +");
			n = Integer.parseInt(nm[0]);
			m = Integer.parseInt(nm[1]);

			mem = new int[n][2];
			arr = new int[n][2];

			//read lines
			int i = 0;
			while ((sCurrentLine = br.readLine()) != null) {
				for (int c = 0; c < n; c++) {
					arr[c][i] = Integer.parseInt(sCurrentLine.split(" +")[c]);
				}
				i++;
			}

			String argument = args[0];

			long startTime = System.nanoTime();

			//recursive
			if (argument.equals("-r")) {
				System.out.println(Math.max(maxPiu(n-1), maxPis(n-1)));
				System.out.println(fcall);
			} 

			//memoized
			else if (argument.equals("-m")) {

				int max = Math.max(maxPium(n-1), maxPism(n-1));
				
				System.out.println(max);
				System.out.println(fcall);
			}

			//iterative
			else if (argument.equals("-i")) {
				for(int x = 0; x < n; x++) {
					maxPisi(x);
					maxPiui(x);
				}
				System.out.println(Math.max(mem[n-1][0], mem[n-1][1]));
			}

			long endTime = System.nanoTime();
			long duration = (endTime - startTime);  
			System.out.println(duration/1000);
	
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	//recursion 
	public static int maxPiu(int i) {
		fcall++;
		if (i == 0) {
				return arr[i][0];
		} else {
				return arr[i][0] + Math.max(maxPiu(i-1), maxPis(i-1)-m);
		}
	}

	public static int maxPis(int i) {
		if (i == 0) {
			return arr[i][1];
		} else {
			return arr[i][1] + Math.max(maxPis(i-1), maxPiu(i-1)-m);
		}
	}

	//mem
	public static int maxPium(int i) {
		if (i == 0) {
			return arr[i][0];
		}

		if (mem[i][0] != 0) {
			return mem[i][0];
		}

		fcall++;

		int max = arr[i][0] + Math.max(maxPium(i-1), maxPism(i-1)-m);
		mem[i][0] = max;
		return max;
	}

	public static int maxPism(int i) {
		if (i == 0) {
			return arr[i][1];
		}

		if (mem[i][1] != 0) {
			return mem[i][1];
		}
		
		int max = arr[i][1] + Math.max(maxPism(i-1), maxPium(i-1)-m);
		mem[i][0] = max;
		return max;
	}

	//iterative
	public static void maxPiui(int i) {
		if (i == 0) {
				mem[i][0] = arr[i][0];
		} else {
				mem[i][0] = arr[i][0] + Math.max(mem[i-1][0], mem[i-1][1]-m);
		}
	}

	public static void maxPisi(int i) {
		if (i == 0) {
			mem[i][1] = arr[i][1];
		} else {
			mem[i][1] = arr[i][1] + Math.max(mem[i-1][1], mem[i-1][0] - m);
		}
	}
	
}