SHARE
TWEET

Untitled

a guest Jan 20th, 2020 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def count_biggest_sum(coins = []):
  2.   cache = []
  3.  
  4.   def fill_cache(coins, i = 0):
  5.     if i >= len(coins) or i < len(cache):
  6.       return
  7.  
  8.     prev_with_bigger = None
  9.     prev_without_bigger = None
  10.  
  11.     max_with = coins[i]
  12.     max_without = 0
  13.  
  14.     indexes_with = [i]
  15.     indexes_without = []
  16.  
  17.     if i - 2 >= 0:
  18.       prev_with_bigger = 0 if cache[i - 2]['values'][0] > cache[i - 2]['values'][1] else 1
  19.  
  20.     if i - 1 >= 0:
  21.       prev_without_bigger = 0 if cache[i - 1]['values'][0] > cache[i - 1]['values'][1] else 1
  22.  
  23.     if prev_with_bigger is not None:
  24.       max_with = max_with + cache[i - 2]['values'][prev_with_bigger]
  25.       indexes_with.extend(cache[i - 2]['indexes'][prev_with_bigger])
  26.  
  27.     if prev_without_bigger is not None:
  28.       max_without = max_without + cache[i - 1]['values'][prev_without_bigger]
  29.       indexes_without.extend(cache[i - 1]['indexes'][prev_without_bigger])
  30.  
  31.     cache.append({
  32.       'values': [max_with, max_without],
  33.       'indexes': [indexes_with, indexes_without]
  34.     })
  35.  
  36.     fill_cache(coins, i + 1)
  37.  
  38.   # Here we have all cache values inserted
  39.   fill_cache(coins)
  40.   biggest_cache = cache[len(cache) - 1]
  41.   bigger = 0 if biggest_cache['values'][0] > biggest_cache['values'][1] else 1
  42.  
  43.   max_sum = biggest_cache['values'][bigger]
  44.   indexes = biggest_cache['indexes'][bigger]
  45.  
  46.   return [max_sum, indexes]
  47.  
  48.  
  49. [max_sum, indexes] = count_biggest_sum([4, 1, 2, 5, 4, 2])
  50. print('Result: ', max_sum)
  51. print('Path: ', indexes)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top