Max Value Gifts

Problem Statement

Given a board with $m \times n$ squares that each square has a gift with a value (value > 0). Suppose you can start taking gifts from square at the top left corner. And each time, you can move down by one square or move right by one square and until you reach the bottom right corner. Each time when you visit a new square, you can take the gift at that square. Calculate the maximum total value of gifts you can take given such a board with gifts. (Assume the board is the right size, and the rows and columns etc are non-zero positive integers)


// Assume the string is Null Terminated 
int getMaxGifts(int[][] values, int rows, int columns){
	// Your Code Here
}

Hint:

Click Here!

Think about how you can solve this problem by solving several subproblems.

Test Cases

Test Case 1

Suppose the board is (top left corner has value 1 and bottom right corner has value 5)

$\begin{bmatrix} 1&10&3&8\\ 12&2&9&6\\ 5&7&4&11\\ 3&7&16&5\\ \end{bmatrix}$

rows = 4 columns = 4

then the function should return the value 53 as we go through the path 1, 12, 5, 7, 7, 16, 5.

Test Case 2

Suppose the board is

$\begin{bmatrix} 1&3&1 \\ 1&5&1\\ 4&2&1\\ \end{bmatrix}$

rows = 3 columns = 3

then the function should return the value 12 as we go through the path 1, 3, 5, 2, 1.

Follow Up Questions To Think About

What is the space and time complexity of the solution?
How can we optimize the amount of memory used?

Click Below to see the Solution

Algorithm

The idea here is to define a sub problem f(i, j) that calculates the maximum total value of gifts we can get when we reached the square at coordinate (i, j). Given this subproblem, we will start computing it from position (0,0). So, when we are calculating the result for position (i,j), we will already have the result at position (i-1, j) and at position (i, j-1) ready. Since only square (i-1, j) and square (i, j-1) can reach square (i, j), then suppose we have f(i-1, j) and f(i, j-1) calculated, we can determine f(i, j) by simply taking the max and adding values[i, j]. This is because that getting max value gift at board[i][j] means that we should be getting max value gift at the previous position it comes from. So, the recurrence relation is f(i,j) = max(f(i-1, j), f(i, j-1)) + gift[i, j].

As we compute the values of f(i, j), we stil store them in a matrix maxValues such that maxValues[i][j] = f(i, j). To actually implement this algorithm, we start at maxValues[0][0] and iterate row by row until we have the values in the entire array. At each iteration and value of i, j, we will have access to f(i, j-1) and f(i-1, j) since the row iteration increases as we go. Therefore, we will be able to successfully compute f(i, j) at each i, j pair.

Now, we simply return f(row-1, columns-1) because that is exaclty the quantity we want to compute.

Code

int getMaxGifts(int[][] values, int rows, int columns){
	int[][] maxValues = new int[rows][columns]; 
	for (int i = 0; i < rows; i++){
		for (int j = 0; j < cols; j++) {
			int left = 0; 
			int up = 0;
			if (i > 0) {
				up = maxValues[i-1][j];  // base cases 
			}
			if (j>0) {
				left = maxValues[i][j-1];
			}
			maxValues[i][j] = Math.max(left, up) + values[i, j]; // recurrence relation
		}
	}
	return maxValues[rows - 1][columns - 1]; // return f(i -1, j -1)
}

Follow Up Question 1 Answer

There are rows * columns values we have to compute, and computing each value takes constant time. So, if we define the size of the board to be $m \times n$ , then the runtime is $O(mn)$ . Similarly, because we have rows * columns subproblems to compute, so the space complexity is also $O(mn)$ .

Follow Up Question 1 Answer

Note that to compute the result for the subproblem at position (i, j), we can only need to the subproblem answer at (i-1, j)and at (i, j-1). So wee can optimize by only memorize the row i-1 and row i. So the space complexity can be improved to $O(n)$ .