Участник:Batyrzhan/K-Concatenation Maximum Sum

Материал из DISCOPAL
< Участник:Batyrzhan
Версия от 22:40, 25 мая 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
class Solution {
    private static final int MOD = 1000000007;
    public int kConcatenationMaxSum(int[] arr, int k) {
        if (k < 3) return getMaxSum(arr, k);
        int maxSum1 = getMaxSum(arr, 1), maxSum2 = getMaxSum(arr, 2);
        long sum = 0;
        for (int num : arr) sum += num;
        return Math.max(Math.max(maxSum1, maxSum2), (int)((maxSum2 + (k - 2) * sum) % MOD));
    }
    private int getMaxSum(int[] arr, int n) {
        int max = 0, sum = 0, min = 0;
        for (int i = 0; i < n; i++) {
            for (int num : arr) {
                sum += num;
                max = Math.max(max, sum - min);
                min = Math.min(min, sum);
            }
        }
        return max;
    }
    }