LeetCode-85 Maximal Rectangle

L
Problem NameMaximal Rectangle
JudgeLeetCode
Problem Linkhttps://leetcode.com/problems/maximal-rectangle/
Algorithms & DSDynamic Programming, Kadane
class Solution { typedef long long int ll; public: int maximalRectangle(vector<vector<char>>& matrix) { ll mat[210][210]; ll cum_sum[210][210]; int x=1,y=1; ll n,m; for(vector<char>i:matrix) { y=1; for(char j:i) { if(j=='1') { mat[x][y]=1; } else mat[x][y]=-1000000; y++; } m=y-1; x++; } n=x-1; for(ll i=0; i<=n; i++)cum_sum[i][0]=0; for(ll j=1; j<=m; j++) { for(ll i=1; i<=n; i++) { cum_sum[i][j]=cum_sum[i-1][j]+mat[i][j]; } } ll ans=0; for(ll i=1; i<=n; i++) { for(ll j=i; j<=n; j++) { ll sum=0; for(ll k=1; k<=m; k++) { ll val=cum_sum[j][k]-cum_sum[i-1][k]; sum+=val; if(sum<0)sum=0; ll dif=abs(j-i)+1; ll tm=sum/dif; ans=min(min(tm,dif),ans); } } } return ans; } };
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!