Max weight path in a triangle
Given an array of array of integers representing a triangle (like pascals triangle), find the max weight path through it, such that you can traverse only from top to bottom using only adjacent integer values
Example
1
2 3
4 5 6
Max path is 1->3->6: 10
Solution
- Use an array to keep track of the max weight moving from previous row to the next row
- For each element in current row, pick the max of the 2 adjacent elements from prev row (prev_row[j-1], prev_row[j])
- Add the max to the current element
- Repeat this until we reach the last row, after each row is processed swap prev and current row, since we no longer need to keep track for prev row information
Code
def max_weight(arr)
return nil if arr.nil?
num_rows = arr.size
prev_row = arr.first
# Evaluate one row at a time
for i in 1..num_rows do
curr_row = arr[i]
curr_row.first += prev_row.first
# Evaluate each element in current row
for j in 1..curr_row.size do
curr_row[j] += max(prev_row[j-1], prev_row[j])
end
curr_row.last += prev_row.last
# Swap rows, since prev_row is no longer required
prev_row = curr_row
end
# Find max weight in the final cummulative sum row
max_weight = 0
curr_row.each do |e|
max_weight = e if e > max_weight
end
max_weight
end
Time complexity
- The total number of elements is 1 + 2 + 3 + .. n = n * (n+1)/2. Therefore overall time complexity is O(n^2).