How to compare integer elements within ArrayList?

Question

I am trying to solve a problem by fetching the maximum number from each row in a triangle. So far am able to generate a triangle but how do I fetch the max number from each row?

Here is my code


private static Integer solve(Triangle triangle)
{
//triangle is extending an ArrayList
System.out.println(triangle);
return 0;
}

This is what am producing so far:

              6
            3  5
          9  7  1
        4  6  8  4

but now I want to get the result which says:

"In this triangle the maximum total is: 6 + 5 + 9 + 8 = 26"

Here is the complete code:

public class HellTriangle {
private static final int TRIANGLE_HEIGHT = 10;


public static void start() {
    Triangle triangle = generateTriangle();
    //System.out.println(triangle);

    long start = System.currentTimeMillis();
    Integer result = solve(triangle);
    long end = System.currentTimeMillis();

    System.out.println("Result:" + result);
    System.out.println("Resolution time: " + (end - start) + "ms");
}

private static Triangle generateTriangle() {
    Triangle triangle = new Triangle();

    Random random = new Random();

    for (int i = 0; i < TRIANGLE_HEIGHT; i++) {

        Row row = new Row();

        for (int j = 0; j <= i; j++) {
            row.add(random.nextInt(100));
        }
        triangle.add(row);
    }
    return triangle;
}

private static class Row extends ArrayList<Integer> {
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < size(); i++) {

            sb.append(String.format("%02d", get(i)));
            //rows.add(get(i));
            if (i < (size() - 1)) {
                sb.append("  ");
            }
        }
        return sb.toString();
    }
}

private static class Triangle extends ArrayList<Row> {

    public String toString() {

        // sb is used to make modification to the String
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < size(); i++) {

            for (int j = 0; j < (TRIANGLE_HEIGHT - 1 - i); j++) {
                sb.append("  ");
            }

            sb.append(get(i));

            if (i < (size() - 1)) {
                sb.append("\n");
            }
        }
        return sb.toString();
    }
}

private static Integer solve(Triangle triangle) {

    System.out.println(triangle);
    return 0;
}

public static void main(String[] args) {
    start();
}
}

Any help would be appreciated!

Answer 1

This is not exactly what you asked for, but I would like to show you a different way to go about this problem. People have done this for me before, and I really appreciated seeing different ways to solve a problems. Good luck with your coding!

Below is the code in its entirety, so you can just copy, paste and run it.

public class SSCCE {
    public static void main(String[] args) {

        // Here you specify the size of your triangle. Change the number dim to
        // whatever you want. The triangle will be represented by a 2d-array.
        final int dim = 5;
        int[][] triangle = new int[dim][dim];

        // Walks through the triangle and fills it with random numbers from 1-9.
        for (int r = 0; r < dim; r++) {
            for (int c = 0; c < r + 1; c++) {
                triangle[r][c] = (int) (9 * Math.random()) + 1;
            }
        }

        // This piece just prints the triangle so you can see what's in it.
        for (int r = 0; r < dim; r++) {
            for (int c = 0; c < r + 1; c++) {
                System.out.print(triangle[r][c] + " ");
            }
            System.out.println();
        }

        // This part finds the maximum of each row. It prints each rows maximum
        // as well as the sum of all the maximums at the end.
        int sum = 0;
        System.out.print("\nIn this triangle the maximum total is: ");
        for (int r = 0; r < dim; r++) {
            int currentMax = 0;
            for (int c = 0; c < r + 1; c++) {
                if (triangle[r][c] > currentMax) {
                    currentMax = triangle[r][c];
                }
            }
            sum += currentMax;
            if (r != 0) {
                System.out.print(" + ");
            }
            System.out.print(currentMax);
        }
        System.out.println(" = " + sum + ".");
    }
}

Output:

9 
9 2 
1 7 3 
1 7 3 3 
5 7 5 1 9 

In this triangle the maximum total is: 9 + 9 + 7 + 7 + 9 = 41.

Answer 2

Here, just change with your solve()

private static void solve(Triangle triangle) {

    System.out.println(triangle);

    ArrayList<Integer> result = new ArrayList<Integer>();
    int total = 0;

    for(Row row  : triangle){
        Collections.sort(row);
        total += row.get(row.size()-1);
        result.add(row.get(row.size()-1));
    }

    for(Integer intr : result)
        System.out.println("Largest elements of the rows: " + intr);
    System.out.println("Total: " + total);
}

Answer 3

Simple-Solution:

1.Add the static list as here:

private static List maxRowVal=new ArrayList();

2.Replace your generateTriangle() function with this:

private static Triangle generateTriangle() 
{
            Triangle triangle = new Triangle();

        Random random = new Random();

        for (int i = 0; i < TRIANGLE_HEIGHT; i++) {

            Row row = new Row();
            int maxTemp=0;
            for (int j = 0; j <= i; j++) {
                int rand=random.nextInt(100);
                row.add(rand);
                if(rand>maxTemp)
                    maxTemp=rand;     //will get max value for the row
            }
            maxRowVal.add(maxTemp);
            triangle.add(row);
        }
        return triangle;
    }

Simple indeed!!

Answer 4

As there is no ordering in your rows and this would lead to O(n) to get the maximum value per row i would look up the maximum value during insertion. Something like that (not tested and you probably have to override the other add methods also, depending on your use case):

public class Row extends ArrayList<Integer> {
    public String toString() {
        ...
    }

    private Integer max = null;

    @Override
    public boolean add(Integer elem) {
        if (elem != null && (max == null || max < elem)) {
            max = elem;
        }
        return super.add(elem);
    }

    public Integer getMax() {
        return max;
    }

}

Answer 5

Try

private static int getTriangleMax(final Triangle rows)
  {
    int max = 0;

    for (final Row row : rows)
    {
      final int rowMax = getRowMax(row);
      max += rowMax;
    }

    return max;
  }

  private static int getRowMax(final Row row)
  {
    int rowMax = Integer.MIN_VALUE;

    for (final Integer integer : row)
    {
      if (rowMax < integer)
      {
        rowMax = integer;
      }
    }

    return rowMax;
  }