这个解决方案对于Max Counters编码挑战有什么问题(What's wrong with this solution for Max Counters codility challenge)

 所以我一直在通过关于编码的测试，并且与“Max Counters”之一卡住了（链接https://codility.com/demo/take-sample-test/max_counters ）。 我的第一个明显的解决方案是以下一个： 
 
def solution(N, A):

    counters = N * [0];    

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;
        elif a == N + 1:
            counters = N * [max(counters)];

    return counters
 
 它工作得很好，但花费了太多时间，因为每次调用max计数器都会填充整个数组。 
 
 因此，我想出了以下解决方案，对于小型输入似乎可以正常工作，但对大中型输入随机提供不正确的结果。 
 
def solution(N, A):

    counters = N * [0];
    current_max = 0;
    last_update = 0;

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;

            if counters[a - 1] < last_update:
                counters[a - 1] = last_update + 1;

            if counters[a - 1] > current_max:
                current_max = counters[a - 1];

        elif a == N + 1:
            last_update = current_max;

    for i in xrange(len(counters)):
        if counters[i] < last_update:
            counters[i] = last_update;           

    return counters
 
 我似乎无法弄清楚它有什么问题。 
 
 编辑：结果 - http://codility.com/demo/results/demoQA7BVQ-NQT/ 

So I've been going through the tests on codility and got bit stuck with the "Max Counters" one (link https://codility.com/demo/take-sample-test/max_counters). My first, and obvious solution was the following one:
 
def solution(N, A):

    counters = N * [0];    

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;
        elif a == N + 1:
            counters = N * [max(counters)];

    return counters
 
which works just fine, but takes too much time, due to the fact that each call to max counters fills an entire array.
 
So I came up with the following solution which seems to work ok for small inputs, but randomly provides incorrect results for medium and large ones.
 
def solution(N, A):

    counters = N * [0];
    current_max = 0;
    last_update = 0;

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;

            if counters[a - 1] < last_update:
                counters[a - 1] = last_update + 1;

            if counters[a - 1] > current_max:
                current_max = counters[a - 1];

        elif a == N + 1:
            last_update = current_max;

    for i in xrange(len(counters)):
        if counters[i] < last_update:
            counters[i] = last_update;           

    return counters
 
I can't seem to figure out what's wrong with it.
 
Edit: Result - http://codility.com/demo/results/demoQA7BVQ-NQT/

原文：https://stackoverflow.com/questions/20506849