Участник:Batyrzhan/K-Concatenation Maximum Sum — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
 
* https://leetcode.com/problems/k-concatenation-maximum-sum
 
* https://leetcode.com/problems/k-concatenation-maximum-sum
  
<code-cpp>
+
<code-java>
 
class Solution {
 
class Solution {
 
     private static final int MOD = 1000000007;
 
     private static final int MOD = 1000000007;
Строка 23: Строка 23:
 
     }
 
     }
 
     }
 
     }
</code-cpp>
+
</code-java>
 
+
[[Участник:StasFomin|StasFomin]] 21:13, 25 мая 2020 (MSK): {{@|Не компилируется как C++, у меня нет времени разбираться, разберитесь}}
+

Текущая версия на 22:40, 25 мая 2020

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;
    }
    }