Cut a sequence of length N into subsequences such that the sum of each subarray is less than M and the cut minimizes the sum of max of each part

Question

Given an integer array sequence a_n of length N, cut the sequence into several parts such that every one of which is a consequtive subsequence of the original sequence.

Every part must satisfy the following:

1. The sum of each part is not greater than a given integer M
2. Find a cut that minimizes the sum of the maximum integer of each part

For example:

input : n = 8, m = 17 arr = [2, 2, 2, 8, 1, 8, 2, 1]
output = 12
explanation: subarrays = [2, 2, 2], [8, 1, 8], [2, 1]
sum = 2 + 8 + 2 = 12

0 <= N <= 100000
each integer is between 0 and 1000000

If no such cut exists, return -1

I believe this is a dynamic programming question, but I am not sure how to approach this.

I am relatively new to coding, and came across this question in an interview which I could not do. I would like to know how to solve it for future reference.

Heres what I tried:

n = 8
m = 17
arr = [2, 2, 2, 8, 1, 8, 2, 1]

biggest_sum, i = 0, 0
while (i < len(arr)):
    seq_sum = 0
    biggest_in_seq = -1
    while (seq_sum <= m and i < len(arr)):
        if (seq_sum + arr[i] <= m ):
            seq_sum += arr[i]
            if (arr[i] > biggest_in_seq):
                biggest_in_seq = arr[i]
            i += 1
        else:
            break
    biggest_sum += biggest_in_seq
if (biggest_sum == 0):
    print(-1)    
else:
    print(biggest_sum)

This givens the result 16, and the subsequences are: [[2, 2, 2, 8, 1], [8, 2, 1]]

Answer 1

Problem is that you are filling every sequence from left to right up to the maximum allowed value m. You should evaluate different options of sequence lengths and minimize the result, which in the example means that the 2 8 values must be in the same sequence.

a possible solution could be:

n = 8
m = 17
arr = [2, 2, 2, 8, 1, 8, 2, 1]

def find_solution(arr, m, n):
    if max(arr)>m:
        return -1

    optimal_seq_length = [0] * n
    optimal_max_sum = [0] * n

    for seq_start in reversed(range(n)):
        seq_len = 0
        seq_sum = 0
        seq_max = 0
        while True:
            seq_len += 1
            seq_end = seq_start + seq_len
            if seq_end > n:
                break
            last_value_in_seq = arr[seq_end - 1]
            seq_sum += last_value_in_seq
            if seq_sum > m:
                break
            seq_max = max(seq_max, last_value_in_seq)
            max_sum_from_next_seq_on = 0 if seq_end >= n else optimal_max_sum[seq_end]
            max_sum = max_sum_from_next_seq_on + seq_max
            if seq_len == 1 or max_sum < optimal_max_sum[seq_start]:
                optimal_max_sum[seq_start] = max_sum
                optimal_seq_length[seq_start] = seq_len

    # create solution list of lists
    solution = []
    seg_start = 0
    while seg_start < n:
        seg_length = optimal_seq_length[seg_start]
        solution.append(arr[seg_start:seg_start+seg_length])
        seg_start += seg_length

    return solution

print(find_solution(arr, m, n))
# [[2, 2, 2], [8, 1, 8], [2, 1]]

Key aspects of my proposal:

• start from a small array (only last element), and make the problem array grow to the front:
  • [1]
  • [2, 1]
  • [8, 2, 1]
  • etc.
• for each of above problem arrays, store:
  • the optimal sum of the maximum of each sequence (optimal_max_sum), which is the value to be minimized
  • the sequence length of the first sequence (optimal_seq_length) to achieve this optimal value
• do this by: for each allowed sequence length starting at the beginning of the problem array:
  • calculate the new max_sum value and add it to previously calculated optimal_max_sum for the part after this sequence
  • keep the smallest max_sum, store it in optimal_max_sum and the associated seq_length in optimal_seq_length