Скачать с ютуб Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming) в хорошем качестве

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

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