Максимальная сумма в k-конкатенации массива
Источник: https://leetcode.com/problems/k-concatenation-maximum-sum/ Дан целочисленный массив arr и целое число k . Сделайте конкатенацию массива k раз . Например, если arr = [1, 2] и k = 3 , то новый массив будет [1, 2, 1, 2, 1, 2] . Надо посчитать максимальную сумму, которую можно получить из какого-либо подмассива этого нового массива. Заметьте, что подмассив может быть нулевой длинны, и тогда сумма его элементов будет рана 0. Ответ сфоррмировать по модулю 10 9 + 7 . Пример 1: Дано: arr = [1,2], k = 3 Результат: 9 (все элементы нового массива) Пример 2: Дано: arr = [1,-2,1], k = 5 Результат: 2 (две подряд идущие 1) Пример 3: Дано: arr = [-1,-2], k = 7 Результат: 0 (все элементы отрицательные, значит максимальную сумму даст пустой подмассив). Ограничения: 1 <= arr.length <= 10 5 1 <= k <= 10 5 -10 4 <= arr[i] <= 10 4 Идея решения Мы можем выделить несколько случаев: Case 1 : когда k == 1 , тогда нам нужно найти только подмассив с максимал...