а сегодня первая проблема hard!

а сегодня первая проблема hard!

Рекурсией ломается?

И примеры неочень, не понятно, можно ли возвращаться по пройденному пути

Сомневаюсь, иначе бы решения не было

Почему?

При положительных узлах можно было бы гулять туда-сюда

Неет

Возвращаться, но не прибавлять значение

Ну, во 2 примере не выгодно идти через -10 -> 9, т.к. будет -1

Понятно. Не, тут именно путь нужен

А если бы там было -10 -> 12, было бы выгодно

Понятно. Не, тут именно путь нужен

На я тоже думаю так, так логичнее

Т.е. где-то начал и идёшь. До какого-то конечного пункта

Назад не возвращаешься

А ты/вы уже решили?

Нет, только прочитал условие

)

Первая мысль пока что: inorder traversal

максимальная сумма пути в левом поддереве, узле и правом поддереве

и отдельно левое / правое поддерево. из них максимум

Рекурсией ломается?

да, ДП (если я правильно понимаю, что такое ДП, а что рекурсия, ахаха) прошло

странный хард. я бы сказал, что это медиум

странный хард. я бы сказал, что это медиум

+

Сейчас доем и попробую с ноги в лоб

Как я понял, надо просто схлопнуть дерево

все-таки, от харда я ожидаю более сложны структур данных, вроде max/min heap и их комбинаций

что-то я не понял. кто-нибудь может объяснить, почему здесь правильный ответ 16, а не 15.

6 + 9 + -3 + 2 + 2

ага, т.е не обязательно идти до конца дерева чтобы собрать целый путь

Да

и это по-вашему не хард? 😄

ладно, ладно 🙂

ещё порешаю

Кто-нибудь может объеснить зачем нужна pair?

На стаке только о плюсах и минусах говорят, а зачем нужна нет

Можно же вектор или массив из 2 элементов сделать,

Postorder прошёл в итоге

Можно же вектор или массив из 2 элементов сделать,

Легковеснее

без лишних методов, проверок

Легковеснее int[2] ?

А у пары есть какие-то свойства?

Да

Легковеснее int[2] ?

Ну, допустим, для удобства тогда

first, second, =, swap

То ты пишешь индексы, а то вот эти слова

"выше уровень абстракции", если говорить умными словами

Ну пока 0 за

@vitkarpov Ждем экперта

Ну пока 0 за

Этого мало разве?

Я догадываюсь

Для удобства скорее всего, но я хочу от плюсовика усляшать почему

В шарпах такое тоже есть

Можно же вектор или массив из 2 элементов сделать,

Как сделать массив или вектор из двух разных типов?

Как сделать массив или вектор из двух разных типов?

Ой, вот это хороший аргумент

НУ тогда struct

Это собственно его цель

Хотя каждый раз структуру делать

Надоест

Struct норм, но у pair например сразу определены операторы сравнения

И можно ту же точку из двух координат легко в мап или сет положить

Для ключа можно использовать, да

Чуть удобнее чем у структуры определять оператор сравнения. С другой стороны, я все равно делаю Point, чтобы читать поля с понятными названиями, а не first и second

В шарпах не так давно появилась возможность задавать названия этим полям. Только там это Item1 и Item2

по умолчанию

С С++17 стандарта можно деструктуризацию делать, как в JS, так что тоже удобно

Я отказался от структуры Point в таком случае :-)

например, (string Name, int Count) user = ("Вася", 5);

Собственно все ассоциативные контейнеры хранят именно pair. Это можно заметить если итерироваться - там first и second. А сделано это как раз потому что надо объединить два разных типа.

Можно и больше объединять - тогда есть tuple

Аналогично и шарп

Есть Tuple и ValueTuple

@vtambourine а как ты через ДП сделал сегодняшнюю задачу?

https://github.com/vtambourine/leetcode-go/blob/master/0124.binary_tree_maximum_path_sum/binary_tree_maximum_path_sum.go

https://github.com/vtambourine/leetcode-go/blob/master/0124.binary_tree_maximum_path_sum/binary_tree_maximum_path_sum.go

А, это dfs получается

У меня так же, но без дополнительной функции максимума. И выходит излишне громозко

https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/603039/C-simple-recursive-postorder-DFS-solution

не уверен. DFS подразумевает стек, а не рекурсивный вызов

не уверен. DFS подразумевает стек, а не рекурсивный вызов

Можно и рекурсивно, и итеративно. Просто разные реализации

окей, тогда я вообще не понимаю, что такое ДП...

Решение бОльшей задачи, используя решения меньших задач.