Problem description:

Give N*N matrix with random amount of money. can only go left-right, top-bottom. Find the path with max amount of money in its way.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<vector<int> maxMoney(vector<vector<int> moneys) {
	// assume: moneys is not null, width and length are equal
	int n = moneys.size();
	if (n == 0)
		return vector<vector<int>();
	// base case
	for (int j = 1; j < n; j++) {
		moneys[0][j] = -(Math.abs(moneys[0][j-1]) + moneys[0][j]);
	}
	for (int i = 1 ; i < n ; i++) {
		moneys[i][0] = moneys[i-1][0] + moneys[i][0];
	}
	for(int i = 1; i < n ; i++) {
		for(int j = 1; j < n ; j++) {
			int top = Math.abs(moneys[i-1][j]) + moneys[i][j];
			int left = Math.abs(moneys[i][j-1]) + moneys[i][j];
			if(top >= left) moneys[i][j] = top;
			else moneys[i][j] = -left;
		} 
	}
	System.out.println("Max path sum = " + Math.abs(moneys[n - 1][n - 1]));
	List<List<Integer>> path = new ArrayList<>();
	int curri = n-1;
	int currj = n-1;
	while (curri > 0 || currj > 0) {
		path.add(Arrays.asList(curri, currj));
		if(moneys[curri][currj] < 0) {
			currj -= 1;
		} else {
			curri -=1;
		}
	}
	path.add(Arrays.asList(0, 0));
	return path;
}

time complexity: $O()$
space complexity: $O()$
reference: