Given a 2D array Blocks[][] consisting of N rows of variable length. The task is to select at most M elements with maximum possible sum from Blocks[][] from either the start or end of a row.
Examples:
Input: N = 3, M = 4
Blocks[][] = {{2, 3, 5}, {-1, 7}, {8, 10}}
Output: 30
Explanation:
Select {5} from 1st row.
Select {7} from 2nd row.
Select {8, 10} from 3rd row.
Input: N = 3, M = 2
Blocks[][] = {{100, 3, -1}, {-1, 7, 10}, {8, 10, 15}}
Output: 115
Explanation:
select {100} from 1st row.
Skip 2nd row.
Select {15} from 3rd row.
Naive Approach: The simplest approach is to iterate through all the rows of the matrix and push all the elements into a vector and sort it. Calculate the sum of last M elements and print it as the required answer.
Time Complexity: O(N * KlogK), where K is the maximum size any block can have.
Auxiliary Space: O(N * K)
Efficient Approach : To optimize the above approach, the idea is to use Dynamic Programming using Memoization. Follow the steps below:
Given N rows and from each row, select any segment from the ith row, say from l to r.
Count of elements in ith row is (r – l + 1) and proceed to the next row.
To calculate the maximum sum, use prefix sum technique in order to calculate the sum.
Initializee a 2D array dp[][], where dp[N][M] stores the maximum sum by selecting at most M elements from N rows.
Consider following two scenarios:
Either skip the current row.
Select any segment from the current row that does not exceed the number of elements selected.
Below is the implementation of the above approach:
// Java program for the above approach
import java.util.*;
public class GFG {
// Funtion to selct m elements
// having maximum sum
public static long
mElementsWithMaxSum(long[][] matrix,
int M, int block,
long[][] dp)
{
// Base case
if (block == matrix.length)
return 0;
// If precomputed subproblem occurred
if (dp[block][M] != -1)
return dp[block][M];
// Either skip the current row
long ans
= mElementsWithMaxSum(matrix, M,
block + 1, dp);
// Iterate through all the possible
// segments of current row
for (int i = 0;
i < matrix[block].length; i++) {
for (int j = i;
j < matrix[block].length; j++) {
// Check if it is possible to select
// elements from i to j
if (j - i + 1 <= M) {
// Compuete the sum of i to j as
// calculated
ans = Math.max(
ans,
matrix[block][j]
- ((i - 1) >= 0
? matrix[block][i - 1]
: 0)
+ mElementsWithMaxSum(
matrix, M - j + i - 1,
block + 1, dp));
}
}
}
// Store the computed answer and return
return dp[block][M] = ans;
}
// Function to precompute the prefix sum
// for every row of the matrix
public static void
preComputing(long[][] matrix, int N)
{
// Preprocessing to calculate sum from i to j
for (int i = 0;
i < N; i++) {
for (int j = 0;
j < matrix[i].length; j++) {
matrix[i][j]
= (j > 0
? matrix[i][j - 1] : 0)
+ matrix[i][j];
}
}
}
// Utility function to selct m elements having
// maximum sum
public static void
mElementsWithMaxSumUtil(long[][] matrix,
int M, int N)
{
// Preprocessing step
preComputing(matrix, N);
// Initialize dp array with -1
long dp[][] = new long[N + 5][M + 5];
for (long i[] : dp)
Arrays.fill(i, -1);
// Stores maximum sum of M elements
long sum = mElementsWithMaxSum(matrix, M,
0, dp);
// Print the sum
System.out.print(sum);
}
// Driver Code
public static void main(String args[])
{
// Given N
int N = 3;
// Given M
int M = 4;
// Given matrix
long[][] matrix
= { { 2, 3, 5 }, { -1, 7 },
{ 8, 10 } };
// Function Call
mElementsWithMaxSumUtil(matrix, M, N);
}
}
Output:
30
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
No comments:
Post a Comment