Associate Technology L2

public class MaximumSumRectangle {

// Function to find the maximum sum rectangle
public static int findMaximumSumRectangle(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;

// Variables to store the final result
int maxSum = Integer.MIN_VALUE;
int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;

for (int left = 0; left < cols; left++) {
int[] temp = new int[rows];

for (int right = left; right < cols; right++) {
// Sum the values in the current column range for each row
for (int i = 0; i < rows; i++) {
temp[i] += matrix[i][right];
}

// Find the maximum sum subarray in temp[]
KadaneResult kadaneResult = kadane(temp);

// Update the maximum sum rectangle if needed
if (kadaneResult.maxSum > maxSum) {
maxSum = kadaneResult.maxSum;
finalLeft = left;
finalRight = right;
finalTop = kadaneResult.start;
finalBottom = kadaneResult.end;
}
}
}

// Print the maximum sum rectangle
System.out.println("Maximum Sum Rectangle:");
for (int i = finalTop; i <= finalBottom; i++) {
for (int j = finalLeft; j <= finalRight; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}

return maxSum;
}

// Function to find the maximum sum subarray in an array using Kadane's algorithm
private static KadaneResult kadane(int[] arr) {
int maxEndingHere = arr[0];
int maxSoFar = arr[0];
int start = 0;
int end = 0;
int tempStart = 0;

for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxEndingHere + arr[i]) {
maxEndingHere = arr[i];
tempStart = i;
} else {
maxEndingHere += arr[i];
}

if (maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
start = tempStart;
end = i;
}
}

return new KadaneResult(maxSoFar, start, end);
}

// Helper class to store the result of Kadane's algorithm
private static class KadaneResult {
int maxSum;
int start;
int end;

KadaneResult(int maxSum, int start, int end) {
this.maxSum = maxSum;
this.start = start;
this.end = end;
}
}

public static void main(String[] args) {
int[][] matrix = {
{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}
};

int maxSum = findMaximumSumRectangle(matrix);
System.out.println("Maximum Sum: " + maxSum);
}
}

While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element that should have come to this place greedily which will give the optimal answer

Follow the below steps to solve the problem:

1) Create a new array and copy the elements of the input array
2) Sort the new array and declare a variable ans equal to 0
3) Run a for loop to traverse the elements
4) If the current element in the sorted array is not equal to the one in the input array then increase the ans by 1
And swap the current element, with the required element at this index
Return ans

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for the predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Follow the steps to implement the approach:

Iterate Through the Array
Calculate an index based on the absolute value of each element.
If the index is equal to ‘n,‘ count it as the largest element.
If the element at the calculated index is negative, add (index – 1) to the result vector and modify the element at that index.
If there are more than one largest element, add ‘n – 1’ to the result vector.
If the result vector is empty, add ‘-1‘ to it.
Otherwise, sort the result vector.
Return the Result Vector

The idea is to put all the opening brackets in the stack. Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration. In the end, if the stack is empty, it means all brackets are balanced or well-formed. Otherwise, they are not balanced.