Problem:
Data:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
Here is my code:
String[] s = getText(18).split("\\s");
int[] a = stringArraytoIntArray(s);
Stack<Integer> stackOfindices = new Stack<Integer>();
// stack of indices (actually the path of indices)
final int maxdepth = 15;
final int size = maxdepth * (maxdepth + 1) / 2;
boolean[] treaded = new boolean[size];
// treaded or not?
Arrays.fill(treaded, false);// not travelled anywhere, this could be avoided since default values and all that, but for clearance I wrote it
int max = 1;// maximum is greater than 1
int depth = 0;// depth to which we have reached
int sum = a[0];// present sum
stackOfindices.push(0);// pushing the index 0
treaded[0] = true;// travelled index 0
boolean shouldadd = true;// used whether to return or whether add to sum
// the present number
// loop:
do {
++depth;// enter a depth
if (depth != maxdepth) {
// choose an undiscovered branch and add to sum while pushing to
// stack
// two paths possible 0,+1
for (int i = 0; i <= 2; i++) {// trying children
if (i == 2) {// if last children
if (stackOfindices.peek() == size) {
return max;
}
// clearing mechanism which clears treaded array for
// entries children since we would be reaching some of
// these children maybe
// later through different paths and we then want these
// to be treated as untreaded
for (int j = 0; j <= 1; j++) {// clear each index of
// children
int clearindex = stackOfindices.peek() + depth + j;
treaded[clearindex] = false;
}
depth -= 2;// now move 2 steps up (since we will dive a
// step at the start so total -1)
sum -= a[stackOfindices.peek()];// subtract from sum
stackOfindices.pop();// remove current index
shouldadd = false;// do not add but return
break;
}
int tryindex = stackOfindices.peek() + depth + i;
// try these index if not the last one
if (!treaded[tryindex]) {
stackOfindices.push(tryindex);// push
treaded[stackOfindices.peek()] = true;// traversed
shouldadd = true;// add the number
break;
// if found a treadable branch exit checking for a new
// index
}
}
// add to sum
if (shouldadd) {
sum += a[stackOfindices.peek()];
}
} else {
if (stackOfindices.peek() == (size - 1)) {
break;
}
// when no further check with max
if (sum > max) {
// System.out.println("="+max);
max = sum;
}
// step back and subtract
depth -= 2;
// since it is going to be increased by one at the start of loop
sum -= a[stackOfindices.peek()];
stackOfindices.pop();
}
} while (true);
return max;
It is/was actually my first DFS implementation. I am unhappy with:
- Large Size of code. I've seen smaller and concise similar approaches.
- Confusing, even after adding comments.
- Code speed is fine, you can improve it if you want
- Other possible improvements you think could be done.
- Don't try to switch it to another algorithm (the reverse working one)
