• API
• FAQ
• Tools
• Archive
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.
Top