Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Začínam od konca a zoberiem posledné 2 riadky. Pre každé číslo na hornom riadku urobím súčet s číslom na spodnom riadku pre ľavú a pravú stranu. Zistím, ktoré číslo je väčšie – súčet s ľavým alebo súčet s pravým. Touto sumou nahradím sčítanec(číslo) v hornom riadku. Potom vymažem posledný riadok a postup opakujem, až kým sa nedostanem na vrchol. Nezaujíma ma celá cesta, len jej súčet
Zadaný príklad:
|
1 2 3 4 |
3 7 4 2 4 6 8 5 9 3 |
Posledné 2 riadky:
Najprv 2 v predposlednom riadku:
|
1 2 |
2 + 8 = 10 2 + 5 = 7 |
10 je viac ako 7 a 2 nahradím číslom 10.
Pre 4:
|
1 2 |
4 + 5 = 9 4 + 9 = 13 |
Nahradím 13
Pre 6:
|
1 2 |
6 + 9 = 15 6 + 3 = 9 |
Nahradím ju 9
Po prvom kroku sa mi zadanie zmení nasledovne:
|
1 2 3 |
3 7 4 10 13 15 |
Po opakovaní postupu:
|
1 2 |
3 20 19 |
A nakoniec
|
1 |
23 |
Všetky riešenia sú dostupné aj na mojom 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(); } } |