class Solution { public static int M = (int)(Math.pow(10, 9) + 7); public long mod(long val){ return val % M; } public long add(long val1 , long val2){ return mod(mod(val1) + mod(val2)); } public long mul(long val1 , long val2){ return mod(mod(val1) * mod(val2)); } public int kConcatenationMaxSum(int[] arr, int k) { //ques 43 of dp playlist , kadanes algo System.out.println(arr.length); if(k == 1){ return Math.max((int)mod(kadanes(arr)) , 0); } else{ //find total sum long sum = 0 ; int n = arr.length; for(int i = 0 ; i < n ; i++) sum = sum + arr[i]; //make an array of double size to store first 2 repetition int narr[] = new int[2*n]; for(int i = 0 ; i < 2*n ; i++) narr[i] = arr[i%n]; //if sum < 0 , find kadanes of first 2 repetition only if(sum < 0){ int MAS = (int)mod(kadanes(narr)); return MAS < 0 ? 0 : MAS; } //if sum >= 0 find kadanes of first and last repetition and add //(k-2) * sum else { int MAS = (int)add(kadanes(narr) ,mul(k-2, sum)); return MAS < 0 ? 0 : MAS; } } } public long kadanes(int[] arr){ int n = arr.length ; long csum = arr[0] , omax = arr[0]; for(int i = 1 ; i < n ; i++){ long val = arr[i]; if(csum > 0) csum = csum + val; else csum = val; omax = Math.max(omax , csum); } return omax; } }