# Maximum rectangle in a matrix

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return *its area*.

```
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length <= 0) return 0;
int n = matrix.length;
int m = matrix[0].length;
int[][] dp = new int[n][m];
int maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0)
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[i][j] = matrix[i][j] == '1' ? (dp[i-1][j] + 1) : 0;
int min = dp[i][j];
for (int k = j; k >= 0; k--) {
if (min == 0) break;
if (dp[i][k] < min) min = dp[i][k];
maxArea = Math.max(maxArea, min * (j - k + 1));
}
}
}
return maxArea;
}
}
```

## Related Problems

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

There is a robot on an m x n grid. The robot is initially located at the **top-left corner** (i.e., grid[0][0]). The robot tries to move to the **bottom-right corner** (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.