Skip to content

Commit dfb7000

Browse files
64json64json
committed
add max_sum_path
1 parent 67a8589 commit dfb7000

File tree

15 files changed

+99
-51
lines changed

15 files changed

+99
-51
lines changed

‎algorithm/etc/dp/config.json

+2-1
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
],
1111
"files": {
1212
"fibonacci": "Fibonacci Sequence",
13-
"sliding_window": "Finding the largest sum of three contiguous number"
13+
"sliding_window": "Finding the largest sum of three contiguous number",
14+
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down"
1415
}
1516
}

‎algorithm/etc/dp/max_sum_path/code.js

+32
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
tracer._print('values = [');
2+
for (var i = 0; i < D.length; i++) {
3+
tracer._print('&nbsp;&nbsp;&nbsp;&nbsp;[' + D[i].join(', ') + ']');
4+
}
5+
tracer._print(']');
6+
tracer._pace(200);
7+
var N = DP.length;
8+
var M = DP[0].length;
9+
for (var i = 0; i < N; i++) {
10+
for (var j = 0; j < M; j++) {
11+
tracer._sleep();
12+
if (i == 0 && j == 0) {
13+
tracer._select(i, j);
14+
DP[i][j] = D[i][j];
15+
tracer._deselect(i, j);
16+
} else if (i == 0) {
17+
tracer._select(i, j - 1);
18+
DP[i][j] = DP[i][j - 1] + D[i][j];
19+
tracer._deselect(i, j - 1);
20+
} else if (j == 0) {
21+
tracer._select(i - 1, j);
22+
DP[i][j] = DP[i - 1][j] + D[i][j];
23+
tracer._deselect(i - 1, j);
24+
} else {
25+
tracer._selectSet([{x: i, y: j - 1}, {x: i - 1, y: j}]);
26+
DP[i][j] = Math.max(DP[i][j - 1], DP[i - 1][j]) + D[i][j];
27+
tracer._deselectSet([{x: i, y: j - 1}, {x: i - 1, y: j}]);
28+
}
29+
tracer._notify(i, j);
30+
}
31+
}
32+
tracer._print('max = ' + DP[N - 1][M - 1]);

‎algorithm/etc/dp/max_sum_path/data.js

+10
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
var tracer = new Array2DTracer();
2+
var D = Array2D.createRandomData(5, 5, 1, 5);
3+
var DP = [];
4+
for (var i = 0; i < D.length; i++) {
5+
DP.push([]);
6+
for (var j = 0; j < D[i].length; j++) {
7+
DP[i].push(999);
8+
}
9+
}
10+
tracer.setData(DP);

‎algorithm/etc/dp/sliding_window/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,3 @@
11
var tracer = new Array1DTracer();
2-
var D = tracer.createRandomData(20, -5, 5);
2+
var D = Array1D.createRandomData(20, -5, 5);
33
tracer.setData(D);

‎algorithm/graph_search/dfs/all_paths/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -6,5 +6,5 @@ var tracer = new GraphTracer();
66
[0, 0, 0, 0, 1],
77
[0, 0, 0, 0, 0]
88
];*/
9-
var G = tracer.createRandomData(5, .75);
9+
var G = Graph.createRandomData(5, .75);
1010
tracer.setData(G);

‎algorithm/graph_search/dfs/shortest_path/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -6,5 +6,5 @@ var tracer = new WeightedGraphTracer();
66
[0, 2, 0, 0, 1],
77
[0, 1, 3, 0, 0]
88
];*/
9-
var G = tracer.createRandomData(10, .3, 1, 9);
9+
var G = WeightedGraph.createRandomData(10, .3, 1, 9);
1010
tracer.setData(G);

‎algorithm/graph_search/dfs/weighted_graph/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -6,5 +6,5 @@ var tracer = new WeightedGraphTracer();
66
[0, 2, 0, 0, 1],
77
[0, 1, 3, 0, 0]
88
];*/
9-
var G = tracer.createRandomData(5, .5);
9+
var G = WeightedGraph.createRandomData(5, .5);
1010
tracer.setData(G);

‎algorithm/sorting/bubble/basic/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,3 @@
11
var tracer = new Array1DTracer();
2-
var D = tracer.createRandomData(15);
2+
var D = Array1D.createRandomData(15);
33
tracer.setData(D);

‎algorithm/sorting/insertion/basic/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,3 @@
11
var tracer = new Array1DTracer();
2-
var D = tracer.createRandomData(15);
2+
var D = Array1D.createRandomData(15);
33
tracer.setData(D);

‎algorithm/sorting/quick/basic/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,3 @@
11
var tracer = new Array1DTracer();
2-
var D = tracer.createRandomData(15);
2+
var D = Array1D.createRandomData(15);
33
tracer.setData(D);

‎algorithm/sorting/selection/basic/data.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,3 @@
11
var tracer = new Array1DTracer();
2-
var D = tracer.createRandomData(15);
2+
var D = Array1D.createRandomData(15);
33
tracer.setData(D);

‎js/module/array1d.js

+4-3
Original file line numberDiff line numberDiff line change
@@ -5,9 +5,10 @@ function Array1DTracer(module) {
55
Array1DTracer.prototype = Object.create(Array2DTracer.prototype);
66
Array1DTracer.prototype.constructor = Array1DTracer;
77

8-
// Override
9-
Array1DTracer.prototype.createRandomData = function (N, min, max) {
10-
return Array2DTracer.prototype.createRandomData.call(this, 1, N, min, max)[0];
8+
var Array1D = {
9+
createRandomData: function (N, min, max) {
10+
return Array2D.createRandomData(1, N, min, max)[0];
11+
}
1112
};
1213

1314
// Override

‎js/module/array2d.js

+13-11
Original file line numberDiff line numberDiff line change
@@ -25,19 +25,21 @@ Array2DTracer.prototype.clear = function () {
2525
clearTableColor();
2626
};
2727

28-
Array2DTracer.prototype.createRandomData = function (N, M, min, max) {
29-
if (!N) N = 10;
30-
if (!M) M = 10;
31-
if (min === undefined) min = 1;
32-
if (max === undefined) max = 9;
33-
var D = [];
34-
for (var i = 0; i < N; i++) {
35-
D.push([]);
36-
for (var j = 0; j < M; j++) {
37-
D[i].push((Math.random() * (max - min + 1) | 0) + min);
28+
var Array2D = {
29+
createRandomData: function (N, M, min, max) {
30+
if (!N) N = 10;
31+
if (!M) M = 10;
32+
if (min === undefined) min = 1;
33+
if (max === undefined) max = 9;
34+
var D = [];
35+
for (var i = 0; i < N; i++) {
36+
D.push([]);
37+
for (var j = 0; j < M; j++) {
38+
D[i].push((Math.random() * (max - min + 1) | 0) + min);
39+
}
3840
}
41+
return D;
3942
}
40-
return D;
4143
};
4244

4345
// Override

‎js/module/graph.js

+13-12
Original file line numberDiff line numberDiff line change
@@ -25,19 +25,20 @@ GraphTracer.prototype.clear = function () {
2525
clearGraphColor();
2626
};
2727

28-
// Override
29-
GraphTracer.prototype.createRandomData = function (N, ratio) {
30-
if (!N) N = 5;
31-
if (!ratio) ratio = .3;
32-
var G = [];
33-
for (var i = 0; i < N; i++) {
34-
G.push([]);
35-
for (var j = 0; j < N; j++) {
36-
if (i == j) G[i].push(0);
37-
else G[i].push((Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0);
28+
var Graph = {
29+
createRandomData: function (N, ratio) {
30+
if (!N) N = 5;
31+
if (!ratio) ratio = .3;
32+
var G = [];
33+
for (var i = 0; i < N; i++) {
34+
G.push([]);
35+
for (var j = 0; j < N; j++) {
36+
if (i == j) G[i].push(0);
37+
else G[i].push((Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0);
38+
}
3839
}
40+
return G;
3941
}
40-
return G;
4142
};
4243

4344
GraphTracer.prototype.setTreeData = function (G, root) {
@@ -85,7 +86,7 @@ GraphTracer.prototype.setTreeData = function (G, root) {
8586
// Override
8687
GraphTracer.prototype.setData = function (G) {
8788
if (Tracer.prototype.setData.call(this, arguments)) return true;
88-
89+
8990
graph.clear();
9091
var nodes = [];
9192
var edges = [];

‎js/module/weighted_graph.js

+17-16
Original file line numberDiff line numberDiff line change
@@ -16,25 +16,26 @@ WeightedGraphTracer.prototype.clear = function () {
1616
clearWeights();
1717
};
1818

19-
// Override
20-
WeightedGraphTracer.prototype.createRandomData = function (N, ratio, min, max) {
21-
if (!N) N = 5;
22-
if (!ratio) ratio = .3;
23-
if (!min) min = 1;
24-
if (!max) max = 5;
25-
var G = [];
26-
for (var i = 0; i < N; i++) {
27-
G.push([]);
28-
for (var j = 0; j < N; j++) {
29-
if (i == j) G[i].push(0);
30-
else if ((Math.random() * (1 / ratio) | 0) == 0) {
31-
G[i].push((Math.random() * (max - min + 1) | 0) + min);
32-
} else {
33-
G[i].push(0);
19+
var WeightedGraph = {
20+
createRandomData: function (N, ratio, min, max) {
21+
if (!N) N = 5;
22+
if (!ratio) ratio = .3;
23+
if (!min) min = 1;
24+
if (!max) max = 5;
25+
var G = [];
26+
for (var i = 0; i < N; i++) {
27+
G.push([]);
28+
for (var j = 0; j < N; j++) {
29+
if (i == j) G[i].push(0);
30+
else if ((Math.random() * (1 / ratio) | 0) == 0) {
31+
G[i].push((Math.random() * (max - min + 1) | 0) + min);
32+
} else {
33+
G[i].push(0);
34+
}
3435
}
3536
}
37+
return G;
3638
}
37-
return G;
3839
};
3940

4041
// Override

0 commit comments

Comments
 (0)