Вам дан массив целых чисел nums с индексами, начинающимися с 0, и целым числом k.
Изначально вы находитесь под индексом 0. На каждом шаге вы можете перепрыгнуть на k шагов вперед, но не можете выпрыгнуть за границу массива. То есть вы можете перейти от индекса i к любой позиции, где [i + 1, min(n - 1, i + k)] содержит две конечные точки.
Ваша цель — достичь последней позиции массива (индекс n — 1), а ваш результат — это сумма всех переданных чисел.
Пожалуйста, верните максимальный балл, который вы можете получить.
Пример 1:
Ввод: числа = [1,-1,-2,4,-7,3], k = 2
Выход: 7
Объяснение: Вы можете выбрать подпоследовательности. [1,-1,4,3] (цифры, выделенные жирным шрифтом выше), а сумма равна 7 。
func maxResult(nums []int, k int) int {
q, n := make([]int, 0), len(nums)
push := func(i int) {
for len(q) > 0 && nums[q[len(q)-1]] < nums[i] {
q = q[:len(q)-1]
}
q = append(q, i)
}
push(0)
for i := 1; i < n; i++ {
for q[0] < i-k {
q = q[1:] // Удалить первый элемент, индекс которого превышает диапазон k
}
nums[i] += nums[q[0]] // Обновление на месте
push(i)
}
return nums[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}