[NEW ALGORITHM] : Maximal Rectangle (DP)

[ananydev]

Issue will be closed if:

1. You mention more than one algorithm. You can create a separate issue for each algorithm once the current one is completed.
2. You propose an algorithm that is already present or has been mentioned in a previous issue.
3. You create a new issue without completing your previous issue.

Note: These actions will be taken seriously. Failure to follow the guidelines may result in the immediate closure of your issue.

---

Name: Maximal Rectangle (DP)

[NEW ALGORITHM]

About:

Propose a new algorithm to be added to the repository

Preprocess Heights: Instead of focusing on individual rows and building height stacks, calculate the cumulative "height" for every 1 in the matrix, row by row. This is similar to the traditional histogram approach, but here we maintain a cumulative sum array for each column as we iterate over each row. This helps us to keep track of vertical continuity of 1s.

Sliding Window Histogram Expansion:

For each row, consider it as the "base" of potential rectangles.
Use a sliding window to determine all possible rectangles within the current row’s "height array." Start with the smallest possible width (1) and expand the width while checking if it’s possible to extend the rectangle upwards.
Dynamic Width & Height Validation: While expanding the width, maintain the minimum height encountered in the sliding window (the limiting factor for height as the rectangle expands sideways).

For each rectangle width w being considered at row r, calculate the maximum possible area based on the minimal height in the window so far:
area

width
×
minHeight
area=width×minHeight
Track the maximum area encountered at each stage of expansion.
Update Maximum Rectangle: As each row is processed with the sliding window and width expansion, update the maximum rectangle area found.

Labels:

new algorithm, gssoc-ext, hacktoberfest, level1

---

Assignees:

• Contributor in GSSoC-ext
• Want to work on it

[ananydev]

@pankaj-bind KINDLY ASSIGN ME THIS . I'LL START WORKING ON IT IMMEDIATELY

[ananydev]

@pankaj-bind pls update !!

[ananydev]

pls update

[ananydev]

kindly update

[pankaj-bind]

assigned