CareerCup

This is an easy question.
this link
onestopinterviewprep.blogspot.com/2014/03/max-apples-that-can-be-collected-in-2d.html
has a similar problem.

I guess the qn should be moving right or down nor right or left ??

I guess it should be right or down, we cannot solve with left or right.

A simple Dp problem.

As you can move right or <b>down</b> only so a cell say (i,j) can be reached from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND (i-1),j] this will make the value at every (i,j) cell as maximum keeping in sync with the fact that only right and downward transitions are allowed.

public class MaxEggCollectionProblem {
	public static void main(String[] args) {
		int[][] eggsMapping = new int[][] { { 2, 4, 8 }, { 5, 6, 3 },
				{ 4, 7, 6 } };

		int numberOfRows = eggsMapping.length;
		int numberofColumns = eggsMapping[0].length;

		printArray(eggsMapping, numberOfRows, numberofColumns);

		// As you can move right or down only so a cell say (i,j) can be reached
		// from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only
		// what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND
		// (i-1),j]
		// this will make the value at every (i,j) cell as maximum keeping in
		// sync with the fact that only right and downward transitions are
		// allowed

		findMaxEggs(eggsMapping, numberOfRows, numberofColumns);
		
		System.out.println("\n\n");
		System.out.println("Max eggs collected at cell 1,2 is " + eggsMapping[1][2]);
		System.out.println("Max eggs collected at cell 2,2 is " + eggsMapping[2][2]);

	}

	private static void printArray(int[][] eggsMapping, int numberOfRows,
			int numberofColumns) {
		System.out.println("===================");

		// Print the array
		for (int i = 0; i < numberOfRows; i++) {
			for (int j = 0; j < numberofColumns; j++) {
				System.out.print(eggsMapping[i][j] + "\t");
			}
			System.out.println("");
		}

	}

	/**
	 * As you can move right or down only so a cell say (i,j) can be reached
	 * from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only
	 * what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND
	 * (i-1),j] this will make the value at every (i,j) cell as maximum keeping
	 * in sync with the fact that only right and downward transitions are
	 * allowed
	 * 
	 * @param eggsMapping
	 * @param numberofColumns
	 * @param numberOfRows
	 */
	private static void findMaxEggs(int[][] eggsMapping, int numberOfRows,
			int numberofColumns) {
		for (int i = 0; i < numberOfRows; i++) {
			for (int j = 0; j < numberofColumns; j++) {

				int leftWeight = -1;
				int topWeight = -1;

				leftWeight = (i - 1) < 0 ? 0 : eggsMapping[i - 1][j]; 
				topWeight = (j - 1) < 0 ? 0 : eggsMapping[i][j-1];
				
				eggsMapping[i][j] += Math.max(leftWeight, topWeight);
			}
		}

		printArray(eggsMapping, numberOfRows, numberofColumns);
	}
}