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:

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!

why don't you use Collections.sort()? Then you will get an ascending order of your integers in your row. Then get the last element in your list for each row, sum up and print it. — anvarik
– anvarik, Commented Jul 17, 2013 at 11:12
@anvarik - I did that but then how do I get the maximum element or a number from the row? — Simple-Solution
– Simple-Solution, Commented Jul 17, 2013 at 11:16

anvarik · Accepted Answer · 2013-07-17 11:36:09Z

1

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);
}

edited Jul 17, 2013 at 11:36

answered Jul 17, 2013 at 11:30

anvarik

6,5075 gold badges41 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dirk Lachowski Over a year ago

By doing so a solve() would destroy the ordering of the triangle rows.

anvarik Over a year ago

yeah well i just copied pasted his solve, then simply move that triangle print to top...

Dirk Lachowski · Accepted Answer · 2013-07-17 11:21:50Z

1

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;
    }

}

answered Jul 17, 2013 at 11:21

Dirk Lachowski

3,1514 gold badges44 silver badges68 bronze badges

Comments

Thinesh Ganeshalingam · Accepted Answer · 2013-07-17 11:21:01Z

0

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;
  }

answered Jul 17, 2013 at 11:21

Thinesh Ganeshalingam

7235 silver badges15 bronze badges

Comments

rahulserver · Accepted Answer · 2013-07-17 11:32:54Z

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!!

Goatcat · Accepted Answer · 2013-07-17 11:44:52Z

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.

Collectives™ on Stack Overflow

How to compare integer elements within ArrayList?

Here is my code

Here is the complete code:

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Here is my code

Here is the complete code:

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related