[LeedCode OJ]#221 Maximal Square

class Solution{public:int maximalSquare(vector<vector<char>>& matrix){int n = matrix.size();if(n==0) return 0;int m = matrix[0].size();int i,j,c;vector<vector<int> > dp,a;dp.resize(n+1),a.resize(n+1);for(i = 0; i<=n; i++){dp[i].resize(m+1);a[i].resize(m+1);}for(i = 0; i<n; i++){for(j = 0; j<m; j++){a[i+1][j+1] = matrix[i][j]-'0';}}int sum = 0;for(i = 1; i<=m; i++){sum+=a[1][i];dp[1][i] = sum;}for(i = 2; i<=n; i++){sum = 0;for(j = 1; j<=m; j++){sum+=a[i][j];dp[i][j]=dp[i-1][j]+sum;}}int maxn = 0;for(i = n; i>0; i–){for(j = m; j>0&&maxn<i*j; j–){if(a[i][j]){int r = 1,c = 1;while(j-c>=0){if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c){if(r==c)maxn = max(maxn,r*c);c++;}elsebreak;}while(i-r>=0&&c>0){if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c){if(r==c)maxn = max(maxn,r*c);r++;}elsec–;}}}}return maxn;}};

，可我，仍在旅行的路上徘徊。等待着每一辆经过的车，让我走到更远的地方。