Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Problem with Project Euler problem 18

1. ## Problem with Project Euler problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle
this is my code but it gives 21 instead of 23 what is wrong in the code thanks
```    public static void main(String[] args) {
List<List<Integer>> twoDim = new ArrayList<List<Integer>>();
int  tempSum;
int temp ;

String[] inputLines = {"3","7 4","2 4 6","8 5 9 3"};

for (String line : inputLines) {
List<Integer> row = new ArrayList<Integer>();

Scanner s = new Scanner(line);
while (s.hasNextInt())

}
int lines = twoDim.size();

for (int i = lines-2 ; i >= 0; i--) {
for (int j = 0; j <= i; j++)
{

}
}
System.out.println(twoDim.get(0).get(0));
}```

2. ## Re: Problem with Project Euler problem 18

While your approach may be clever - then again, maybe TOO clever - it is not easy to understand or troubleshoot. I suggest you simplify the part of your program that chooses which value of the next row to add to the total so that you can add test lines to see what is going wrong. Think about how you'd do it in your head or with pencil and paper and code that.

3. ## Re: Problem with Project Euler problem 18

Choosing the maximum adjacent value is not guaranteed to give the maximum sum from top to bottom (as demonstrated here).

Here's a more obvious example:

1
1 1
2 1 1
1 1 8 9

Your approach will choose 1 + 1 + 2 + 1, but the best approach is 1 + 1 + 1 + 9.

If you want to solve this problem the "lazy way", you can use a brute force solver and try every path. As the problem hint suggests, this will work here, but not on problem 67.

There's a more efficient solution, though (as the problem suggested). As a hint, think about the problem going backwards.