Having trouble solving an exercise from CodeChef [easy]

Question

So, basically I'm feeling incredibly dumb, because of this exercise, I've spent like 4 or 5 hours trying to code it, and so far I've not been successful.

I have come to the realization that this one is easier to solve with a tree traversal using the Longest Path approach, But I'm not sure (Could you please confirm this to me.), could be over-kill since it's supposed to be one of the easy problems, So Could you please help me with some guidance or basic steps or algorithm approaches on how to solve this one? all kinds of help is certainly appreciated.

PS. I usually post some code about what I've done so far, but I believe that to this point everything has been so wrong that I prefer to start from scratch, at least in terms of ideas.

Thanks.

As per-request, here's the Code I typed according to the accepted answer to solve the Exercise:

def get_max_sum(matrix)
  (1...matrix.length).each do |index|  
    flag = 0  
    matrix[index].each_with_index do |e, i|    
      add = (matrix[index-1][flag] > matrix[index-1][flag+1]) ? matrix[index-1][flag] : matrix[index-1][flag+1]
      e += add
      matrix[index][i] = e
      flag = flag + 1
    end    
  end
  matrix[-1][0]
end

Where the matrix param is an array of arrays, each one representing a row from the triangle.

Answer 1

NOTE: The problem statement in the original post assumes a strickly right triangle:

on each path the next number is located on the row below,
more precisely either directly below or below and one place to the right.

Also look at the examples they provide to confirm this.

ANSWER:

• 1] use a two dimensional array to store the triangle

• recompute the triangle based on their rules

• walk the last row of the triangle -- i.e. the base -- to find the max value.

CODE:

import java.util.Arrays;

public class NumberTriangle {

    //MAIN IS FOR TESTING ONLY
public static void main(String[] ars) {
    int[][] input = { { 1 }, { 4, 8 }, { 9, 8, 7 }, { 1, 3, 6, 9 },
            { 7, 5, 2, 7, 3 } };

    int max = compute(input);// answer: max length
    // not necessary; but shows new triangle
    for (int[] A : input)
        System.out.println(Arrays.toString(A));

    // print the answer
    System.out.println("Largest number: " + max);
}

    //THIS IS THE SOLUTION
public static int compute(int[][] input) {
    //compute new triangle
    for (int y = 1; y < input.length; y++)
        for (int x = 0; x < input[y].length; x++) {
            int first = x - 1 > 0 ? x - 1 : 0;
            int last = x < input[y - 1].length ? x
                    : input[y - 1].length - 1;
            int max = Math.max(input[y - 1][last], input[y - 1][first]);
            input[y][x] += max;
        }
    //extract max value;
    int max = -1;
    int lastRow = input[input.length - 1].length;
    for (int x = 0, y = input.length - 1; x < lastRow; x++)
        if (max < input[y][x])
            max = input[y][x];
    return max;
}// compute
}

Answer of test case:

[1]
[5, 9]
[14, 17, 16]
[15, 20, 23, 25]
[22, 25, 25, 32, 28]

Largest number: 32

Answer 2

This problem is easy if you start from the bottom and work your way up. Consider the triangle

   1
  1 2
 4 1 2
2 3 1 1

Look at the next-to-last row. If by some path through the triangle you arrive at 4, you will move right to the 3, giving a sum of 7 (plus whatever is in the path above it). If you've reached 1, you will move left to the 3, giving a sum of 4 (plus whatever is in the path above it). If you're at 2, you can move either way for a sum of 3 (plus whatever is in the path above it). Thus, by replacing the next-to-last row with the sums, the triangle

  1
 1 2
7 4 3

will have the same maximum-sum path as the original triangle. Now do the same process recursively on the reduced triangle. From 1 on the next-to-last row move left to 7, giving a sum of 8, and from 2 move left to 4, giving a sum of 6. The reduced triangle now looks like

 1
8 6

Finally, from 1 on the next-to-last row move left to 8, giving a sum of 9, which is the answer to the problem.

There is also a method of working from the top down. At each step you replace each number in the triangle with the maximum-sum of any path leading to that number. Starting from the top, the triangle starts

1

Then the second row is replaced by its sums

 1
2 3

Then the third row

  1
 2 3
6 4 5

And finally the fourth row

   1
  2 3
 6 4 5
8 9 6 6

The answer is the largest sum in the bottom row, which is 9. I've always found the top-down approach harder to manage than the bottom-up approach, but the two algorithms are dual to each other, so it's your choice which to implement. The top-down approach does have the advantage that you can accumulate the next row as you're reading the data; with the bottom-up approach, you have to read and store the entire input before you compute any of the sums.

I'll leave it to you to write the code. When you do, remember that you only need to store two rows at a time, the previous row and the next row. Which is previous and which is next depends on whether you're working top-down or bottom-up -- the previous row is the row you just filled in and the next row is the row you're currently working on, which means that if you're working top-down the next row has one more sum than the previous row, and if you're working bottom-up the next row has one less sum than the previous row. Please post your code when you get it working, so others can learn from your effort.

By the way, this problem originally comes from Project Euler. Code Chef stole it from them, apparently without attribution, which really isn't a very nice thing to do.

Answer 3

A longest-path-finding approach feels like the wrong approach to me since every path will be N-1 edges long. I think I'd start the approach by pretending like the input is a binary tree and finding the largest element in the tree -- find the largest sum of the bottom two rows, memoize the results in the penultimate row, and then move up another row. (I hope that makes some kind of sense...)