Geek asks and answers

Problems solving exercise with CodeChef [easy]

So, basically I feel incredibly stupid, because this exercise , I spent 4 or 5 hours trying to code it, and so far I have failed.

I came to the realization that this is easier to solve by traversing the tree using the Longest Path method , but I couldn’t ( Could you confirm this to me. ), Since it should be one of the simple problems. Therefore, could you please help me with some guidelines or basic steps or approaches to the algorithm? on how to solve this problem? any help is certainly appreciated.

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

Thank.

As requested, here is the Code I printed in accordance with the accepted answer for solving 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 parameter is an array of arrays, each of which represents a line from a triangle.

+3
source share
3 answers

This problem is simple if you start from the bottom and make your way up. Consider a triangle

   1
  1 2
 4 1 2
2 3 1 1

. - 4, 3, 7 ( , ). 1, 3, 4 ( , ). 2, 3 ( , ). , ,

  1
 1 2
7 4 3

, . . 1 7, 8, 2 4, 6.

 1
8 6

, 1 8, 9, .

. , . ,

1


 1
2 3


  1
 2 3
6 4 5

, ,

   1
  2 3
 6 4 5
8 9 6 6

- , 9. , , , , , . , ; , , .

, . , , , . : , - - , , - , , , , , , , , . , , , .

, Project Euler. Code Chef , -, , .

+6

. :

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.

, , .

:

  • 1]

  • - .. - .

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
}

:

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

Largest number: 32
+1

The longest search path is the wrong approach to me, as each path will be the long edge of N-1. I think that I would start using this approach, pretending that the input is a binary tree and finding the largest element in the tree - find the largest sum of the bottom two rows, remember the results in the penultimate row, and then move another row. (Hope this makes some sense ...)

0
source

More articles: