Maximum Sum Of MNon Overlapping Subarrays | Recursion | Dynamic Programming

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution of Maximum Sum Of M Non-Overlapping Sub-arrays of size k. In this problem,

1. You are given an array(arr) of positive numbers and two numbers M and K.
2. You have to find the maximum sum of M non-overlapping subarrays of size K.
3. The size of given array(arr) is greater than M*K.

Expected Time Complexity - O(n*m)
Expected Space Complexity - O(n*m).



.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer

[hemantchauhan]

You people explain in hindi is the best thing about your channel .. and with such an ease keep doing good work AMEEN

[kunalkishore]

Tabular solution ->
public static int arr, int m, int k) {
int n = arr.length;
int[] psum = new int[n];

// Calculate prefix sums for subarrays of size K
int sum = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
psum[0] = sum;
for (int i = k; i < n; i++) {
sum = sum + arr[i] - arr[i - k];
psum[i - k + 1] = sum;
}

// Create DP table
int[][] dp = new int[n + 1][m + 1];

// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j]; // Case: not taking the current subarray
if (i >= k) {
dp[i][j] = Math.max(dp[i][j], psum[i - k] + dp[i - k][j - 1]);
}
}
}

return dp[n][m];
}

[Rajkumar-jkus]

Can you prepare the same video in English ?

[jeevangautam]

sir recursive solution t.l.e de raha h...

[rajshinde]

Explain in English it's not relavant in hindi