Help to solve this question

help
1

Given an integer sequence (a) of length N, you are to cut the sequence into several parts such that every one of which is a consecutive subsequence of the original sequence. Every part must satisfy this-the sum of the integers in the part is not greater than a given integer M. You are to find a cut that minimizes the sum of the maximum integer of each part.

Input

Given N(0 <N’s 100 000), M, and N integers describes the integer sequence. Every Integer in the sequence is between 0 and 1 000 000 inclusively.

Output

Output one integer which is the minimum sum of the maximum integer of each part. If no such cutting exist output-1.

sample TC1:
N = 8
M = 17
sequence = [2,2,2,8,1,8,2,1]
expected answer: 12

sample TC2:
N = 28
M = 20
sequence = [1,21,4,9,20,6,11,27,12,21,22,16,13,9,1,8,13,10,9,4,11,7,28,9,13,26,17,18]
don’t know expected answer

2 
def valid_cut(sequence, M, max_sum):
    current_sum = 0
    max_value = float('-inf')
    parts = 1
    
    for num in sequence:
        max_value = max(max_value, num)
        current_sum += num
        
        if current_sum > max_sum:
            current_sum = num
            parts += 1
            
    return parts <= M

def min_max_sum(sequence, M):
    left, right = max(sequence), sum(sequence)
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if valid_cut(sequence, M, mid):
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return result
  1. Define a function valid_cut that checks if it’s possible to cut the sequence such that the sum of the maximum integers in each part is less than or equal to the given integer M.
  2. Use binary search to find the minimum possible value of the maximum sum.
  3. In each iteration of the binary search, check if it’s possible to cut the sequence using the current mid value. If it’s possible, update the answer and continue the search in the lower half of the range.
  4. Finally, return the minimum possible value of the maximum sum.