Можно ли быть лучше, чем O (N + M) для урока Codility MaxCounters, используя Python? ⇐ Python

[Anonymous]

This is the code I am using for the Codility lesson: MaxCounters

def solution(N, A): counters = [0] * N max_c = 0 for el in A: if el >= 1 and el N: counters = [max_c] * N return counters Every test passes but the last one ("all max_counter operations") times out after 7 seconds so the result is just 88% with time complexity of O(N+M).

Is it possible to improve the time complexity of the algorithm and get 100% test result using Python?
The MaxCounters task
You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

Источник: https://stackoverflow.com/questions/588 ... s-using-py