You are viewing a single comment's thread. Return to all comments →
DP solution with O(n) time and O(1) space complexity (no need to use array to store dp value) Explaination in the comments
def cost(b) low = 0 # low[i] is max cost using first i items, ending with 1 at i-th position high = 0 # high[i] is max cost using first i items, ending with b[i] at i-th position (1..b.length - 1).each do |i| pre_low = low # previous low value pre_high = high # previous high value low = [pre_low, pre_high + (b[i - 1] - 1).abs].max high = [pre_low + (b[i] - 1).abs, pre_high + (b[i] - b[i - 1]).abs].max end [low, high].max end
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Cost
You are viewing a single comment's thread. Return to all comments →
DP solution with O(n) time and O(1) space complexity (no need to use array to store dp value) Explaination in the comments