Best Improvement Period of at Least K Intervals
Amazonâ—Ź MediumFULLTIMEPHONE SCREENProblem statement
A machine learning team tracks how a recommendation model changes over n consecutive time intervals. You are given an integer array changes of length n, where changes[i] is the change in recommendation quality during interval i compared with the interval before it. A positive value is an improvement and a negative value is a decline. You are also given an integer k.
Choose a non-empty period of consecutive intervals [i, j], where 0 <= i <= j < n. The period must contain at least k intervals, so j - i + 1 >= k. Its cumulative improvement is:
-changes[i] + changes[i + 1] + ... + changes[j]In other words, the first change in the period is subtracted and every later change is added. A period with only one interval has a cumulative improvement of -changes[i].
Return the maximum cumulative improvement over all valid periods. The answer can be negative.
Function
maxImprovementPeriod(changes: int[], k: int) → intExamples
Example 1
changes = [3,-2,5,-1,4]k = 2return = 10Choose the period [1, 4], which has 4 intervals. Its first change -2 is subtracted, so the score is -(-2) + 5 + (-1) + 4 = 10.
Starting on a decline helps here, because subtracting a negative change adds to the score. The full period [0, 4] scores only -3 + (-2) + 5 + (-1) + 4 = 3, and no other period of at least 2 intervals scores more than 10.
Example 2
changes = [-3,-1]k = 1return = 3With k = 1, one interval is allowed. The period [0, 0] scores -(-3) = 3.
The other choices score -(-1) = 1 for [1, 1] and -(-3) + (-1) = 2 for [0, 1], so the answer is 3.
Example 3
changes = [5,1,-4,2]k = 3return = -3The valid periods are [0, 2] with score -5 + 1 + (-4) = -8, [1, 3] with score -1 + (-4) + 2 = -3, and [0, 3] with score -5 + 1 + (-4) + 2 = -6.
Every valid period scores below zero, and the best one is [1, 3], so the answer is -3.
Constraints
1 <= changes.length <= 10^5-10^4 <= changes[i] <= 10^41 <= k <= changes.length