Я решил проблему двойного среза на Codility, когда я решил немного подумать о том, какое возможное решение могло бы быть для проблемы тройной суммы срезов. К сожалению, я не мог придумать для этого хорошего эффективного решения. Я взял на себя смелость модифицировать исходную задачу и сформулировать задачу Triple Slice.
Дан непустой массив A, состоящий из N целых чисел.
Тройка (W, X, Y, Z), такой что 0 ≤ W
Сумма тройного среза (W, X, Y, Z) равна сумме A [W + 1] + A [W + 2] + ... + A [X - 1] + A [X + 1] + A [X + 2] + ... + A [Y - 1] + A [Y + 1] + A [Y + 2] + ... + A [Z - 1].
Например, массив A такой, что:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
A[8] = 1
содержит следующую тройку примера срезы:
triple slice (0, 3, 5, 7), sum is 2 + 6 + 4 + (-1) = 11,
triple slice (0, 3, 6, 8), sum is 2 + 6 + 4 + 5 + 2 = 19
Цель состоит в том, чтобы найти максимальную сумму любого тройного среза.
Напишите функцию:
int solution(vector<int> &A);
, которая при непустом массив A, состоящий из N целых чисел, возвращает максимальную сумму любого тройного среза.
Например, если:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
A[8] = 1
функция должна возвращать 19 , потому что нет сумма тройного среза массива A больше 19.
Напишите эффективный алгоритм для следующих предположений: * 10 29 *
N - целое число в диапазоне [4..100,000]; каждый элемент массива A является целым числом в диапазоне [-10,000..10,000].