Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)

Опубликовано: 06 Февраль 2019
на канале: Back To Back SWE

77,450

2.5k

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given a 2D matrix with integer values (and including at least 1 positive value) find the sub-rectangle with the largest sum.

I want to step you through all of the tough mental leaps to solve this problem.

Complexities

Let rows = the number of rows
Let cols = the number of columns

Naive Runtime: Ω(rows^2 * cols^2)

Explanation:

There are rows * cols possible start points and for each rows * cols possible start points we will do O(rows * cols) work, this causes us to have our time lower bounded by the amount of time it takes to explore all top left and bottom right combinations so that we can explore all 2D rectangles in the matrix.

This is not even including getting the sum for each 2D rectangle we set bounds for (we can do it in O(rows).

Similar to this problem https://leetcode.com/problems/range-s...

Optimal Solution Runtime (2D Kadane's): O(cols^2 * rows)

We will try all combinations of left and right ending points for the possible 2D rectangle.

For that O(col^2) work we will do O(row) work to run Kadane's on the row sum cache (for each left-right combination of the possible final rectangle).

So the cumulative work will be O(cols^2 * rows).

Space will be O(rows) because of the vertical rows sum cache.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial

Tuschar Roy:    / tusharroy2525

GeeksForGeeks:    / @geeksforgeeksvideos

Jarvis Johnson:    / vsympathyv

Success In Tech:    / @successintech

Смотрите видео Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming) онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Back To Back SWE 06 Февраль 2019, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 77,450 раз и оно понравилось 2.5 тысяч людям.