Hackerrank – Problem description
The problem description – Hackerrank.
Solution
I read and store all number into lists by rows.
I start from the bottom and take last 2 lines. I sum a number from upper row with numbers from lower row on the left and right side. I do it for every number in the upper row. Then I find the greatest sum – with left or with right. I use this greatest sum and switch all numbers in the upper row with it for every item. I delete bottom line and continue the process until I reach only top of the triangle.
Given example:
|
1 2 3 4 |
3 7 4 2 4 6 8 5 9 3 |
Last 2 rows:
Start with 2:
|
1 2 |
2 + 8 = 10 2 + 5 = 7 |
10 is greater than 7 and 2 is replaced with 10.
4:
|
1 2 |
4 + 5 = 9 4 + 9 = 13 |
It is replaced with 13
6:
|
1 2 |
6 + 9 = 15 6 + 3 = 9 |
Replaced with 9
There is a following state after first iteration:
|
1 2 3 |
3 7 4 10 13 15 |
Second iteration:
|
1 2 |
3 20 19 |
I the end:
|
1 |
23 |
I created solution in:
All solutions are also available on my GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class MaximumPathSum1 { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int tests = stdin.nextInt(); for (int t = 0; t < tests; t++) { List<List<Long>> rows = new ArrayList<>(); int rowCount = stdin.nextInt(); for (int i = 0; i < rowCount; i++) { List<Long> row = new ArrayList<>(); for (int j = 0; j < i + 1; j++) { row.add(stdin.nextLong()); } rows.add(row); } for (int i = rows.size() - 2; i >= 0; i--) { List<Long> tempRow = new ArrayList<>(); for (int j = 0; j < rows.get(i).size(); j++) { List<Long> upperRow = rows.get(i); List<Long> bottomRow = rows.get(i + 1); long sumLeft = upperRow.get(j) + bottomRow.get(j); long sumRight = upperRow.get(j) + bottomRow.get(j + 1); long max = sumLeft > sumRight ? sumLeft : sumRight; tempRow.add(max); } rows.remove(i + 1); rows.set(i, tempRow); } System.out.println(rows.get(0).get(0)); } stdin.close(); } } |