Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (tabulization)
Sat Apr 01 2023 12:59:00 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
int n = arr.length;
int[] winSum = new int[n];
for(int i = 0; i <= n - k; i++){
if(i == 0){
for(int j = 0; j < k; j++){
winSum[i] += arr[j];
}
}else{
winSum[i] = winSum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
}
int[][] dp = new int[m + 1][arr.length + 1];
for(int i = 0; i < dp.length; i++){
for(int j = 0; j < dp[0].length; j++){
if(i == 0){
dp[i][j] = 0;
}else if(j < i * k){
dp[i][j] = 0;
}else{
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - k] + winSum[j - k]);
}
}
}
return dp[m][arr.length];
content_copyCOPY
https://www.geeksforgeeks.org/max-sum-of-m-non-overlapping-subarrays-of-size-k/
Comments