In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 22nd
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]
In this problem you should submit a function as described. Inside the function do not print anything that was not asked!
The name of the .py source file you submit to Mooshak should NOT start with a digit (you will get an error if you submit it like that).
Leonard Hofstadter is once again deep into his physics experiments at Caltech. Each trial produces a long list of energy readings, represented as integers. Positive values indicate stable, successful reactions, while negative ones show instability (often caused by Sheldon interrupting mid-test). Zeros are neutral and do not count as either positive or negative.
To identify the most stable period of his experiment, Leonard wants to find the contiguous sequence of exactly k readings that contains the highest number of positive values. Can you help him?
Write a function stable(k, lst) that receives an integer k and a list of integers lst, returning the the maximum number of positive values in any contiguous sublist of size k.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ k ≤ 50 000 | Size of sublists to consider | |
| k ≤ |lst| ≤ 50 000 | Number of elements in the list | |
| -1000 ≤ lst[i] ≤ 1000 | Readings in the list |
NOTE: the limits are high and you must have an efficient solution.
If your code simply tries all possible sublists and for each of them you iterate through all elements of the sublist, it will result in a Time Limit Exceeded.
| Example Function Calls | Example Output |
print(stable(3, [-1, -1, 2, -3, 1, -5])) print(stable(4, [1, 2, 3, 4, 5, 6])) print(stable(5, [-1, -2, 1, 1, 0, 3, 0, -4])) |
2 4 3 |
Explanation of the first example
The answer is 2. There are 4 possible contiguous sublists of size 3:
Explanation of the second example
The answer is 4. All sublists of size 4 have 4 positive values.
Explanation of the third example
The answer is 3. There are two sublists of size 5 with 3 positive numbers: [-2, 1, 1, 0, 3] and [1, 1, 0, 3, 0]