Максимальная сумма подмассива размера k

Максимальная сумма подмассива размера k

Условие задачи

Дан массив положительных чисел и положительное число k. Найдите максимальную сумму среди всех непрерывных подмассивов размера k.

Пример 1:

1
2
3

Вход: [2, 1, 5, 1, 3, 2], k=3
Выход: 9
Пояснение: максимальную сумму имеет подмассив [5, 1, 3].

Пример 2:

1
2
3

Вход: [2, 3, 4, 1, 5], k=2
Выход: 7
Пояснение: максимальную сумму имеет подмассив [3, 4].

Решение

В полном переборе можно начинать с каждого индекса и складывать следующие k элементов. Его временная сложность равна \(O(N \cdot k)\).

Более эффективное решение использует сумму предыдущего окна размера k. Чтобы сдвинуть окно на один элемент вправо, нужно:

  1. Прибавить новый элемент, вошедший в окно.
  2. Вычесть первый элемент предыдущего окна, который из него вышел.

Так мы не вычисляем сумму пересекающейся части двух соседних окон повторно.

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

package main

import "fmt"

func findMaxSumSubarray(k int, arr []int) int {
	if k <= 0 || k > len(arr) {
		return 0
	}

	windowSum := 0
	maxSum := 0
	windowStart := 0

	for windowEnd, value := range arr {
		windowSum += value

		if windowEnd >= k-1 {
			if windowStart == 0 || windowSum > maxSum {
				maxSum = windowSum
			}
			windowSum -= arr[windowStart]
			windowStart++
		}
	}

	return maxSum
}

func main() {
	fmt.Println("Максимальная сумма подмассива размера k:", findMaxSumSubarray(3, []int{2, 1, 5, 1, 3, 2}))
	fmt.Println("Максимальная сумма подмассива размера k:", findMaxSumSubarray(2, []int{2, 3, 4, 1, 5}))
}

Вывод:

1
2

Максимальная сумма подмассива размера k: 9
Максимальная сумма подмассива размера k: 7

Временная сложность

Временная сложность алгоритма равна \(O(N)\), где \(N\) — количество элементов массива.

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).