package leetcode;

/**
 * https://leetcode.com/problems/k-concatenation-maximum-sum/
 */
public class Problem1191 {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long totalSum = 0;
        int prefixSum = 0;
        for (int a : arr) {
            totalSum += a;
        }
        // Kadene's algorithm.
        long max = 0;
        long maxSoFar = 0;
        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(arr[i], (maxSoFar + arr[i]));
            max = Math.max(max, maxSoFar);
        }
        long answer = max;
        if (totalSum > 0) {
            answer += totalSum * (k - 1);
        } else {
            answer += prefixSum;
        }
        return (int) answer % 1_000_000_007;
    }

    public static void main(String[] args) {
        Problem1191 prob = new Problem1191();
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,2}, 3)); // 9
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,-2,1}, 5)); // 2
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,-2,4}, 2)); // 7
//        System.out.println(prob.kConcatenationMaxSum(new int[]{5,-10,6}, 4)); // 13
        System.out.println(prob.kConcatenationMaxSum(new int[]{5,-10,4}, 3)); // 9
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,3-2,5,8}, 2)); // 30
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,3-2,5,8}, 3)); // 45
//        System.out.println(prob.kConcatenationMaxSum(new int[]{-1,-2}, 7)); // 0
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,2,-3}, 3)); // 3
//        System.out.println(prob.kConcatenationMaxSum(new int[]{1,2,-3,4}, 3)); // 12
    }
}

@@ -204,35 +204,8 @@
     
-int prefixSum = 0;%0A        
 for 
@@ -241,16 +241,288 @@
 otal
+Sum += a;%0A        %7D%0A        int prefixSum = 0;%0A        int i = 0;%0A        while (i %3C arr.length && arr%5Bi%5D %3E= 0) %7B%0A            prefixSum += arr%5Bi++%5D;%0A        %7D%0A        int suffixSum = 0;%0A        i = arr.length - 1;%0A        while (i %3E= 0 && arr%5Bi%5D %3E= 0) %7B%0A            suffix
 Sum += a
 ;%0A  
@@ -509,32 +509,39 @@
   suffixSum += a
+rr%5Bi--%5D
 ;%0A        %7D%0A    
@@ -550,17 +550,17 @@
   // Kad
-e
+a
 ne's alg
@@ -629,20 +629,16 @@
    for (
-int 
 i = 0; i
@@ -797,14 +797,8 @@
 swer
- = max
 ;%0A  
@@ -839,86 +839,297 @@
     
-answer += totalSum * (k - 1);%0A        %7D else %7B%0A            answer += prefixSum
+long max1 = max + (totalSum * (k - 1));%0A            long max2 = (prefixSum + suffixSum) + (totalSum * (k - 2));%0A            answer = Math.max(max1, max2);%0A        %7D else %7B%0A            long max1 = max;%0A            long max2 = prefixSum + suffixSum;%0A            answer = Math.max(max1, max2)
 ;%0A  
@@ -1614,16 +1614,18 @@
 ; // 13%0A
+//
         
@@ -2129,16 +2129,233 @@
 ; // 12%0A
+//        System.out.println(prob.kConcatenationMaxSum(new int%5B%5D%7B-5,4,-4,-3,5,-3%7D, 3)); // 5%0A        System.out.println(prob.kConcatenationMaxSum(new int%5B%5D%7B-9,13,4,-16,-12,-16,3,-7,5,-16,16,8,-1,-13,15,3%7D, 6)); // 36%0A
     %7D%0A%7D%0A

Update problem 1191