Максимальная сумма в k-конкатенации массива

Источник: https://leetcode.com/problems/k-concatenation-maximum-sum/

Дан целочисленный массив arr и целое число k. Сделайте конкатенацию массива k раз.

Например, если arr = [1, 2] иk = 3, то новый массив будет [1, 2, 1, 2, 1, 2].

Надо посчитать максимальную сумму, которую можно получить из какого-либо подмассива этого нового массива. Заметьте, что подмассив может быть нулевой длинны, и тогда сумма его элементов будет рана 0.

Ответ сфоррмировать по модулю 109 + 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 <= 105
• 1 <= k <= 105
• -104 <= arr[i] <= 104

Идея решения

Мы можем выделить несколько случаев:
Case 1: когда k == 1, тогда нам нужно найти только подмассив с максимальной суммой внутри исходного массива (используем алгоритм Кадана)
Case 2: когда k > 1:

• Case2(1): когда sum >= 0 (и мы допускаем наличие неположительных элементов также): тогда в итоговую сумму войдут почти все элементы нового массива (полученного в результате конкатенации). Какие именно это будут элементы? Представим массив в виде:
  prefix, middle, suffix
  где конкатенация suffix, prefix дает максимальную сумму, а middle уменьшает эту максимальнцю сумму.
  Тогда при k-конкатенации:
  prefix, middle, suffix, prefix, middle, suffix, ... prefix, middle, suffix
  для достижения максимальной суммы нам нужно взять suffix из первого повторения, prefix - из последнего, и всю остальную сумму элементов без изменений между ними.
  А это (k-2)*sum + prefix + suffix
  Поскольку sum>0, то она будет увеличивать итоговый результат.
• Case2(2): когда sum < 0: тогда (k-2)*sum будет только уменьшать результат, то есть мы можем взять только prefix и suffix.
• Заметим, что в обеих варициях случая Case2, еужно сравнить результат и по Кадану тоже.
  

Имплементация

public int kConcatenationMaxSum(int[] arr, int k) {       
        int mod=1000000007;
        int n=arr.length;
        long presum=0,premax=0,sufsum=0,sufmax=0,cursum=0,curmax=0;
        for(int i=0;i<n;i++){    
 
            // prefix sum
            presum+=arr[i];
            premax=Math.max(premax,presum);

            //suffix sum
            sufsum+=arr[n-1-i];
            sufmax=Math.max(sufmax,sufsum);
           
            //Kadane's Algorithm
            cursum=Math.max(0,cursum)+arr[i];
            curmax=Math.max(curmax,cursum);

        }
        long max=Math.max(curmax,premax+sufmax+Math.max(0,presum*(k-2))); // prefix sum(presum) will be the sum of the complete array after entire traversal...
        return (int)((k==1?curmax:max)%mod);
    }
}