Google Screening question 2024 | L4 | Bangalore India | Reject

I gave my interview last week with Google.

Problem:

You are given a sequence of positive integers sequence. Your goal is to divide this sequence into parts non-empty contiguous subsequences. Among these parts subsequences, the number of subsequences whose sum of elements is at least threshold will be called the score. Find the maximum score.

sequence = [1, 4, 2, 8]
parts = 3
threshold = 6

Output:
2


sequence = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
parts = 5
threshold = 2

Output:
5

expected time complexity was O(nlogn)