uva- 836 - Largest Submatrix Solution

uva- 836 - Largest Submatrix 

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>

using namespace std;

int calculate_max_histogram_area(int *arr,int len){
stack<int> st;
int i, max, temp,temp_sum,cur_index,sum;
temp = 0;
max = 0;
temp_sum = 0;
for (i = 0; i< len; i++){
if (arr[i]>0 && arr[i] >= temp){
temp = arr[i];
st.push(i);
}
else{
temp = arr[i];
while (true){
if (st.empty())
break;
cur_index = st.top();
if (arr[cur_index] == temp)
break;
st.pop();
sum = arr[cur_index] * (i - cur_index);
if (sum > max){
max = sum;
}
}
if (i < len && arr[i]>0)
st.push(i);
}
}
while (!st.empty()){
cur_index = st.top();
st.pop();
sum = arr[cur_index] * (i - cur_index);
if (sum > max){
max = sum;
}
}
return max;
}

int calculate_max_sub_matrix(string *input, int n){
int temp[25],i,j,k,temp_sum,max;
string str,*start;
max = 0;
for (i = 0; i < n; i++){
start = input + i;
fill(temp, temp + n, 0);
for (j = i; j < n; j++){
str = *start;
for (k = 0; k < n; k++){
if (str[k] == '1'){
temp[k]++;
}else{
temp[k] = 0;
}
}
temp_sum = calculate_max_histogram_area(temp, n);
if (temp_sum > max)
max = temp_sum;
start++;
}
}
return max;
}


int main(){
int n, i, j,test_case;
bool flag = false;
string input[25],str;
cin >> test_case;
getchar();
getline(cin, str);
while (test_case--){
if (flag)
cout << endl;
flag = true;
n = 0;
while (true){
getline(cin, str);
if (str.length() == 0)
break;
input[n++] = str;
}
cout<<calculate_max_sub_matrix(input, n)<<endl;
}
return 0;
}