Сервер кометы Python

Для меня все объяснения здесь были ужасны, так как я не получил часть поиска / сортировки. Как мы ищем / сортируем, было неясно.

Мы все знаем, что нам нужно построить prefixSum, что означает sum of all elems from 0 to i with modulo m

Я думаю, то, что мы ищем, ясно. Зная, что subarray[i][j] = (prefix[i] - prefix[j] + m) % m (с указанием суммы по модулю от индекса i до j), наши максимумы при заданном префиксе [i] всегда являются тем префиксом [j], который максимально приближен к префиксу [i], но немного больше.

например. для m = 8, префикс [i] равен 5, мы ищем следующее значение после 5, которое находится в нашем prefixArray.

Для эффективного поиска (бинарный поиск) мы сортируем префиксы.

Что мы не можем сделать, так это сначала построить prefixSum, а затем выполнить итерацию снова от 0 до n и искать индекс в отсортированном массиве префиксов, потому что мы можем найти и endIndex, который меньше, чем наш startIndex, что не годится.

Следовательно, мы делаем итерацию от 0 до n, указывая endIndex нашей потенциальной максимальной суммы подмассива, а затем просматриваем наш отсортированный префиксный массив (который в начале пуст), который содержит отсортированные префиксы между 0 и endIndex.

def maximumSum(coll, m):
    n = len(coll)
    maxSum, prefixSum = 0, 0
    sortedPrefixes = []

    for endIndex in range(n):
        prefixSum = (prefixSum + coll[endIndex]) % m
        maxSum = max(maxSum, prefixSum)

        startIndex = bisect.bisect_right(sortedPrefixes, prefixSum)
        if startIndex < len(sortedPrefixes): 
            maxSum = max(maxSum, prefixSum - sortedPrefixes[startIndex] + m)

        bisect.insort(sortedPrefixes, prefixSum)

    return maxSum