Q43 K-Concatenation Maximum Sum - LeetCode 1191
Wed Apr 05 2023 12:20:03 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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;
}
}
content_copyCOPY
https://leetcode.com/problems/k-concatenation-maximum-sum/solutions/382889/java-java-solution-with-explanation/
Comments