Some notes too big to put into a comment (though this doesn't suggest an obvious algorithm):
The punch line (EDITED): At least two vertices of the maximum area rectangle must lie on the boundary of the polygon (i.e. along an edge, or at a vertex). And if the maximum area rectangle is not a square, then at least three vertices must lie on the boundary of the polygon.
I proved it to myself in four steps:
Note #1: At least one vertex of the maximum area rectangle will always lie on the boundary of the polygon. This is pretty obvious, but a proof could go like this (by contradiction): Suppose you had a "maximal" rectangle with no vertex on the boundary of the polygon. That means there would be at least a little room around each of its vertices. So you could expand your rectangle a bit, contradicting its maximality.
Note #2: At least two vertices of the maximum area rectangle will always lie on the boundary of the polygon. A proof could go like this (again by contradiction): Suppose you had a "maximal" rectangle with only one vertex on the boundary (guaranteed by Note #1). Consider the two edges not adjacent to that vertex. Since their endpoints are NOT on the boundary, there's a little room around each. So either of those edges could be "extruded" a bit, expanding the polygon's area and contradicting its maximality.
Note #3: There are two diagonally opposite vertices of the maximum area rectangle that lie on the boundary of the polygon. (We know from Note #2 that there are at least two, but not necessarily that they're across from each other.) But again by contradiction, if the only two boundary vertices were adjacent, then the opposite edge (neither of whose vertices are on the boundary) could be extruded a little bit, increasing the area of the rectangle and contradicting its maximality.
Note #4: (EDITED) If the maximum area rectangle is not a square, then three of its vertices will lie on the boundary of the polygon.
To prove, suppose that's not the case, i.e. that the maximum area rectangle is not a square, but only two of its vertices are on the boundary of the polygon. I'll show how to construct a bigger rectangle, contradicting the maximality.
Call the vertices of the rectangle A, B, C, and D. Without loss of generality, assume that B and D are the two that are on the polygon boundary. Since A and C are on the interior of the polygon, there's some wiggle room around them (represented with circles around A and C in the picture below). Now draw a circle around the rectangle, and slide points A and C a little bit around the circle by the same amount (to make A' and C', pictured below) so that the new rectangle A'BC'D is more square than the original rectangle. This process creates a new rectangle that is also within the original polygon and has a larger area. This is a contradiction, so the proof is done.
To believe that proof, you have to convince yourself that the area of a rectangle inscribed in a circle increases as it becomes "more square" (i.e. the difference between the edge lengths gets smaller). You also need the polygon to be convex so that the new lines are all within it. And there are probably other little details getting swept under the rug, but I'm fairly sure they all work out.
You're using the wrong tool for filling the hole: You're using the "Delete Ring" tool, but you should be using "Add Feature".
"Delete Ring" is used for deleting an interior ring of a single polygon feature (like the hole in a donut polygon). However, all your features are simple polygons consisting of only an exterior ring, so when you try to draw a large polygon to capture the empty space between your features, you get the "Could not snap segment" error message, as the tool can't find an interior ring to delete where you clicked.
In your case, "filling a hole" actually means "adding a feature that covers the extent not covered by any of the other features in the layer". To do that, you only need to set "Avoid intersections" in the Snapping options (the snapping itself doesn't have to be activated, and neither does the topological editing), and then create a new feature by generously drawing a polygon around the empty space (i.e. around the hole).
Best Answer
Since you are dealing with holes, you could replace such polygons with a filled version. If the polygon has an inner ring, take the outter ring and create a new temporary polygon, then check if it contains others. If yes, using the original polygon, check that it doesn't intersect the smaller one