Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import kotlin.math.max
- fun findMaxDrawSequenceLinear2(results: List<Int>): Int {
- val gapToItsFirstOccurrence = mutableMapOf<Int, Int>()
- var maxLength = 0
- // Разница в очках. 0 означает ничью.
- var gap = 0
- // изначально у нас ничья для полуинтервала [0;0)
- gapToItsFirstOccurrence[gap] = 0
- // Начинаем с единицы, полуинтервал не включает в себя правое значение i
- for (i in 1..results.size) {
- val temp = results[i - 1]
- if (temp == 0) {
- gap--
- } else if (temp == 1) {
- gap++
- }
- // Идея в том, что самая длинная ничейная сессия будет равна максимальной длине полуинтервала, у которого
- // совпадает разница в начале полуинтервала и для каждого уникального значения разницы будет сохраняться
- // индекс начала полуинтервала
- val firstOccurrence = gapToItsFirstOccurrence.getOrPut(gap) { i }
- maxLength = max(maxLength, (i - firstOccurrence))
- }
- return maxLength
- }
- fun main() {
- val reader = System.`in`.bufferedReader()
- val count = reader.readLine().toInt()
- if (count == 0) {
- println(0)
- } else {
- val input = reader.readLine().split(" ")
- .map { it.toInt() }
- println(findMaxDrawSequenceLinear2(input))
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement