fork(1) download
copy 
  1. # https://stackoverflow.com/questions/78359610/split-array-of-integers-into-subarrays-with-the-biggest-sum-of-difference-betwee
  2.  
  3.  
  4. # Code by https://stackoverflow.com/users/585411/btilly
  5.  
  6. from collections import deque
  7.  
  8.  
  9. def window_mins_maxes (size, array):
  10.         min_values = deque()
  11.         min_positions = deque()
  12.         max_values = deque()
  13.         max_positions = deque()
  14.  
  15.         for i, value in enumerate(array):
  16.             if size <= i:
  17.                 yield (i, min_values[0], max_values[0])
  18.                 if min_positions[0] <= i - size:
  19.                     min_values.popleft()
  20.                     min_positions.popleft()
  21.  
  22.                 if max_positions[0] <= i - size:
  23.                     max_values.popleft()
  24.                     max_positions.popleft()
  25.  
  26.             while 0 < len(min_values) and value <= min_values[-1]:
  27.                 min_values.pop()
  28.                 min_positions.pop()
  29.             min_values.append(value)
  30.             min_positions.append(i)
  31.  
  32.             while 0 < len(max_values) and max_values[-1] <= value:
  33.                 max_values.pop()
  34.                 max_positions.pop()
  35.             max_values.append(value)
  36.             max_positions.append(i)
  37.  
  38.         yield (len(array), min_values[0], max_values[0])
  39.  
  40.  
  41. def partition_array(numbers, min_len, max_len):
  42.         if max_len < min_len or len(numbers) < min_len:
  43.             return (None, None)
  44.  
  45.         best_weight = [None for _ in numbers]
  46.         prev_index = [None for _ in numbers]
  47.  
  48.         # Need an extra entry for off of the end of the array.
  49.         best_weight.append(None)
  50.         prev_index.append(None)
  51.  
  52.         best_weight[0] = 0
  53.  
  54.         for i, min_value, max_value in window_mins_maxes(min_len, numbers):
  55.             window_start_weight = best_weight[i - min_len]
  56.             if window_start_weight is not None:
  57.                 j = i
  58.                 while j - i < max_len - min_len and j < len(numbers):
  59.                     new_weight = window_start_weight + max_value - min_value
  60.                     if best_weight[j] is None or best_weight[j] < new_weight:
  61.                         best_weight[j] = new_weight
  62.                         prev_index[j] = i - min_len
  63.  
  64.                     if numbers[j] < min_value:
  65.                         min_value = numbers[j]
  66.                     if max_value < numbers[j]:
  67.                         max_value = numbers[j]
  68.                     j += 1
  69.  
  70.                 # And fill in the longest value.
  71.                 new_weight = window_start_weight + max_value - min_value
  72.                 if best_weight[j] is None or best_weight[j] < new_weight:
  73.                     best_weight[j] = new_weight
  74.                     prev_index[j] = i - min_len
  75.  
  76.         if best_weight[-1] is None:
  77.             return (None, None)
  78.         else:
  79.             path = [len(numbers)]
  80.             while prev_index[path[-1]] is not None:
  81.                 path.append(prev_index[path[-1]])
  82.             path = list(reversed(path))
  83.             partitioned = [numbers[path[i]:path[i+1]] for i in range(len(path)-1)]
  84.             return (best_weight[-1], partitioned)
  85.  
  86. # End code by https://stackoverflow.com/users/585411/btilly
  87.  
  88.  
  89. # Code by https://stackoverflow.com/users/2034787/%d7%92%d7%9c%d7%a2%d7%93-%d7%91%d7%a8%d7%a7%d7%9f
  90.  
  91.  
  92. import collections
  93.  
  94.  
  95. debug = False
  96.  
  97.  
  98. # O(n) method to get maximum value
  99. # of the dp table within an index range.
  100. # Could be done in O(log n) with a tree.
  101. def get_max_dp(dp, l, r):
  102.   if r == -1:
  103.     return (0, -1)
  104.   if r < 0:
  105.     return (-float("inf"), -1)
  106.  
  107.   max_val = 0 if l == -1 else dp[l]
  108.   index = l
  109.  
  110.   for i in range(l + 1, r + 1):
  111.     if dp[i] > max_val:
  112.       max_val, index = dp[i], i
  113.  
  114.   return (max_val, index)
  115.  
  116.  
  117. # Updates the queue of max values and
  118. # returns the index in the list for the current
  119. # max in the range [i - a + 1, i]
  120. def update_and_get_maxs(maxs, A, i, a, b):
  121.   while maxs and maxs[0] <= i - b:
  122.     maxs.popleft()
  123.   while maxs and A[i] >= A[maxs[-1]]:
  124.     maxs.pop()
  125.   maxs.append(i)
  126.   for j in range(len(maxs)):
  127.     if maxs[j] > i - a:
  128.       return j
  129.  
  130.  
  131. # Updates the queue of min values and
  132. # returns the index in the list for the current
  133. # min in the range [i - a + 1, i]
  134. def update_and_get_mins(mins, A, i, a, b):
  135.   while mins and mins[0] <= i - b:
  136.     mins.popleft()
  137.   while mins and A[i] <= A[mins[-1]]:
  138.     mins.pop()
  139.   mins.append(i)
  140.   for j in range(len(mins)):
  141.     if mins[j] > i - a:
  142.       return j
  143.  
  144.  
  145. # O(n) method to get the best of all windows
  146. # tracked. Could be maintained in O(log n) and
  147. # queried in O(1).
  148. def get_max_from_leftmosts(A, leftmosts):
  149.   best = -float("inf")
  150.   for (t, max_idx, min_idx, dp_idx) in leftmosts:
  151.     best = max(best, t)
  152.   return best
  153.  
  154.  
  155. # Method to get the left (lower) bound index
  156. # for the choice of dp value for a window.
  157. def get_left(A, leftmosts, j, i, a, b):
  158.   if A[leftmosts[j+1][1]] == A[leftmosts[j][1]]:
  159.     return leftmosts[j][2]
  160.   elif A[leftmosts[j+1][2]] != A[leftmosts[j][2]]:
  161.     return max(leftmosts[j][1], leftmosts[j][2])
  162.   else:
  163.     return leftmosts[j][1]
  164.  
  165.  
  166. # Main method
  167. def f(A, a, b):
  168.   dp = [-float("inf")] * len(A)
  169.   maxs = collections.deque()
  170.   mins = collections.deque()
  171.  
  172.   # A list of relevant windows stored as tuples:
  173.   # [value, max index, min index, dp choice for window]
  174.   leftmosts = collections.deque()
  175.  
  176.   # Previous (max, min) for the [i - a, i] window
  177.   prev = (None, None)
  178.  
  179.   def print_state():
  180.     print(f"dp: {dp}")
  181.     print(f"maxs: {maxs}")
  182.     print(f"mins: {mins}")
  183.     print(f"leftmosts: {leftmosts}")
  184.     print(f"prev: {prev}")
  185.  
  186.   iterations = 0
  187.  
  188.   for i in range(len(A)):
  189.     if debug:
  190.       print(f"\ni: {i}")
  191.  
  192.     mx_a_idx = update_and_get_maxs(maxs, A, i, a, b)
  193.     mn_a_idx = update_and_get_mins(mins, A, i, a, b)
  194.     if debug:
  195.       print(f"mx_a_idx: {mx_a_idx}")
  196.       print(f"mn_a_idx: {mn_a_idx}")
  197.  
  198.     curr_max_idx = maxs[mx_a_idx]
  199.     curr_min_idx = mins[mn_a_idx]
  200.     if debug:
  201.       print(f"curr_max_idx: {curr_max_idx}")
  202.       print(f"curr_min_idx: {curr_min_idx}")
  203.  
  204.     curr = (curr_max_idx, curr_min_idx)
  205.  
  206.     # New max or min
  207.     if i + 1 == a or (i + 1 > a and prev != curr):
  208.       leftmosts.append([
  209.           None,
  210.           curr_max_idx,
  211.           curr_min_idx,
  212.           None])
  213.  
  214.       for j in range(len(leftmosts) - 2, - 1, -1):
  215.         [t, max_idx, min_idx, dp_idx] = leftmosts[j]
  216.  
  217.         # Similar to the queues for maxes and mins --
  218.         # the new max or min should carry through to all
  219.         # preceding window choices while it's dominant.
  220.         should_update = (A[curr_max_idx] >= A[max_idx]
  221.              or A[curr_min_idx] <= A[min_idx])
  222.  
  223.         if should_update:
  224.           # Crude count of iterations to try to evaluate
  225.           # time complexity of the overall method.
  226.           iterations += 1
  227.  
  228.           if A[curr_max_idx] >= A[max_idx]:
  229.             leftmosts[j][1] = curr_max_idx
  230.           if A[curr_min_idx] <= A[min_idx]:
  231.             leftmosts[j][2] = curr_min_idx
  232.  
  233.         # If two windows now have the same max and min,
  234.         # remove the window since the dp choice can simply 
  235.         # extend to the rightmost window.
  236.         if (A[leftmosts[j][1]] == A[leftmosts[j+1][1]]
  237.              and A[leftmosts[j][2]] == A[leftmosts[j+1][2]]):
  238.           del leftmosts[j]
  239.         # Otherwise, we can use this updated window to
  240.         # update the dp choice for the window to its right.
  241.         else:
  242.           r = min(i - a, leftmosts[j+1][1] - 1,
  243.               leftmosts[j+1][2] - 1)
  244.           l = get_left(A, leftmosts, j, i, a, b)
  245.           if debug:
  246.             print(f"(j, l, r): {(j, l, r)}")
  247.           max_dp, max_dp_idx = get_max_dp(dp, l, r)
  248.           leftmosts[j+1][0] = (A[leftmosts[j+1][1]]
  249.               - A[leftmosts[j+1][2]] + max_dp)
  250.           leftmosts[j+1][3] = max_dp_idx
  251.  
  252.         if not should_update:
  253.           break
  254.  
  255.     # Remove out-of-bounds windows
  256.     if leftmosts and (leftmosts[0][1] <= i - b
  257.         or leftmosts[0][2] <= i - b):
  258.       leftmosts.popleft()
  259.  
  260.     # Regardless of if the first window, [i - a + 1, i], has
  261.     # a new max or min, we need to update its choice of
  262.     # dp since we are shifting the window bounds to the
  263.     # right.
  264.     if len(leftmosts) > 1:
  265.       r = min(i - a, leftmosts[-1][1] - 1,
  266.               leftmosts[-1][2] - 1)
  267.       l = get_left(A, leftmosts, -2, i, a, b)
  268.       if debug:
  269.         print(f"(j, l, r): {(-2, l, r)}")
  270.       max_dp, max_dp_idx = get_max_dp(dp, l, r)
  271.       leftmosts[-1][0] = (A[leftmosts[-1][1]]
  272.           - A[leftmosts[-1][2]] + max_dp)
  273.       leftmosts[-1][3] = max_dp_idx
  274.  
  275.     # Update the dp choice for the leftmost window since
  276.     # the previous choice could now be out of bounds.
  277.     if leftmosts:
  278.       r = min(i - a, leftmosts[0][1] - 1, leftmosts[0][2] - 1)
  279.       l = max(i - b, -1)
  280.       if debug:
  281.         print(f"(j, l, r): {(-1, l, r)}")
  282.       max_dp, max_dp_idx = get_max_dp(dp, l, r)
  283.       leftmosts[0][0] = (A[leftmosts[0][1]]
  284.           - A[leftmosts[0][2]] + max_dp)
  285.       leftmosts[0][3] = max_dp_idx
  286.  
  287.     # Save the result for the current dp index 
  288.     if i + 1 >= a:
  289.       dp[i] = get_max_from_leftmosts(A, leftmosts)
  290.  
  291.     if debug:
  292.       print_state()
  293.  
  294.     prev = curr
  295.  
  296.   # Crude method to detect if complexity could be
  297.   # reaching O(n^2).
  298.   if iterations > 3 * len(A):
  299.     print((iterations, len(A), a, b, A))
  300.  
  301.   return dp[-1]
  302.  
  303.  
  304. import random
  305.  
  306. num_tests = 500
  307. max_n = 500
  308. max_val = 10000
  309.  
  310. for _ in range(num_tests):
  311.   n = random.randint(2, max_n)
  312.   A = [random.randint(1, max_val) for _ in range(n)]
  313.   a = random.randint(2, n)
  314.   b = random.randint(a, n)
  315.   left = partition_array(A, a, b)
  316.   right = f(A, a, b)
  317.  
  318.   if not (left[0] is None and right == -float("inf")) and left[0] != right:
  319.     print((A, a, b, left, right))
  320.     break
Success #stdin #stdout 2.95s 10164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lVXrJM
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!