Question: I'm trying to find the algorithm efficiently solving this problem:  Given an unsorted array of numbers, you need to divide it into several subarrays of length from a to b, so that the sum of differences between the minimum and maximum numbers in each of the subarrays is the greatest. The order of the numbers must be preserved. Examples: a = 3, b = 7 input: [5, 8, 4, 5, 1, 3, 5, 1, 3, 1] answer: [[5, 8, 4], [5, 1, 3], [5, 1, 3, 1]] (diff sum is 12) a = 3, b = 4 input: [1, 6, 2, 2, 5, 2, 8, 1, 5, 6] answer: [[1, 6, 2], [2, 5, 2, 8], [1, 5, 6]] (diff sum is 16) a = 4, b = 5 input: [5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2] answer: splitting is impossible   The only solution I've come up with so far is trying all of the possible subarray combinations. from collections import deque def partition_array(numbers, min_len, max_len): max_diff_subarray = None queue = deque() for end in range(min_len - 1, max_len): if end < len(numbers): diff = max(numbers[0:end + 1]) - min(numbers[0:end + 1]) queue.append(Subarray(previous=None, start=0, end=end, diff_sum=diff)) while queue: subarray = queue.popleft() if subarray.end == len(numbers) - 1: if max_diff_subarray is None: max_diff_subarray = subarray elif max_diff_subarray.diff_sum < subarray.diff_sum: max_diff_subarray = subarray continue start = subarray.end + 1 for end in range(start + min_len - 1, start + max_len): if end < len(numbers): diff = max(numbers[start:end + 1]) - min(numbers[start:end + 1]) queue.append(Subarray(previous=subarray, start=start, end=end, diff_sum=subarray.diff_sum + diff)) else: break return max_diff_subarray class Subarray: def __init__(self, previous=None, start=0, end=0, diff_sum=0): self.previous = previous self.start = start self.end = end self.diff_sum = diff_sum numbers = [5, 8, 4, 5, 1, 3, 5, 1, 3, 1] a = 3 b = 7 result = partition_array(numbers, a, b) print(result.diff_sum)  Are there any more time efficient solutions?

Answer: First let's solve a simpler problem. Let's run through an array, and give mins and maxes for all windows of fixed size. def window_mins_maxes (size, array): min_values = deque() min_positions = deque() max_values = deque() max_positions = deque() for i, value in enumerate(array): if size <= i: yield (i, min_values[0], max_values[0]) if min_positions[0] <= i - size: min_values.popleft() min_positions.popleft() if max_positions[0] <= i - size: max_values.popleft() max_positions.popleft() while 0 < len(min_values) and value <= min_values[-1]: min_values.pop() min_positions.pop() min_values.append(value) min_positions.append(i) while 0 < len(max_values) and max_values[-1] <= value: max_values.pop() max_positions.pop() max_values.append(value) max_positions.append(i) yield (len(array), min_values[0], max_values[0])  This clearly takes memory O(size). What's less obvious is that it takes time O(n) to process an array of length n. But we can see that with amortized analysis. To each element we'll attribute the cost of checking the possible value that is smaller than it, the cost of some later element checking that it should be removed, and the cost of being added. That accounts for all operations (though this isn't the order that they happen) and is a fixed amount of work per element. Also note that the memory needed for this part of the solution fits within O(n). So far I'd consider this a well-known dynamic programming problem. Now let's make it more challenging. We will tackle the partition problem as a traditional dynamic programming problem. We'll build up an array best_weight of the best partition to that point, and prev_index of the start of the previous partition ending just before that point. To build it up, we'll use the above algorithm to take a previous partition and add one of min_len to it. If it is better than the previous, we'll save its information in those arrays. We'll then scan forward from that partition and do that up to max_len. Then we move on to the next possible start of a partition. When we're done we'll find the answer from that code. Here is what that looks like: def partition_array(numbers, min_len, max_len): if max_len < min_len or len(numbers) < min_len: return (None, None) best_weight = [None for _ in numbers] prev_index = [None for _ in numbers] # Need an extra entry for off of the end of the array. best_weight.append(None) prev_index.append(None) best_weight[0] = 0 for i, min_value, max_value in window_mins_maxes(min_len, numbers): window_start_weight = best_weight[i - min_len] if window_start_weight is not None: j = i while j - i < max_len - min_len and j < len(numbers): new_weight = window_start_weight + max_value - min_value if best_weight[j] is None or best_weight[j] < new_weight: best_weight[j] = new_weight prev_index[j] = i - min_len if numbers[j] < min_value: min_value = numbers[j] if max_value < numbers[j]: max_value = numbers[j] j += 1 # And fill in the longest value. new_weight = window_start_weight + max_value - min_value if best_weight[j] is None or best_weight[j] < new_weight: best_weight[j] = new_weight prev_index[j] = i - min_len if best_weight[-1] is None: return (None, None) else: path = [len(numbers)] while prev_index[path[-1]] is not None: path.append(prev_index[path[-1]]) path = list(reversed(path)) partitioned = [numbers[path[i]:path[i+1]] for i in range(len(path)-1)] return (best_weight[-1], partitioned)  Note that we do O(1) work for each possible start and length. And so that is time O((max_len + 1 - min_len)*n). And the data structures we used are all bounded above by O(n) in size. Giving the overall efficiency that I promised in the comments. Now let's test it. print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1], 3, 7)) print(partition_array([1, 6, 2, 2, 5, 2, 8, 1, 5, 6], 3, 4)) print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2], 4, 5))  And the output is: (12, [[5, 8, 4], [5, 1, 3], [5, 1, 3, 1]]) (16, [[1, 6, 2], [2, 5, 2, 8], [1, 5, 6]]) (None, None)