836

This problem also can be solved using Dynamic Programming.

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

string *str = new string [50];
int N;

int kaadanealgo(int a,int b)
{
	int line[50];
	int max_end_here=0;
	int max_so_far=0;

	for(int i=0;i<N;i++)
	{
		line[i] = 0;
		for(int j=a;j<=b;j++)
		{
			if(str[j][i]=='0')
				line[i]+=-1000000;
			else
				line[i]+=(str[j][i]-'0');
		}
	}


	for(int i=0;i<N;i++)
	{
		max_end_here+=line[i];

		if(max_end_here<0)
		max_end_here = 0;

		if(max_end_here>max_so_far)
			max_so_far = max_end_here;
	}

	return max_so_far;
}
int main()
{
	int t,m,mx;
	string s,a;
	bool c =false;
	cin>>t;
	getchar();

	while(t--)
	{
		getline(cin,s);

		getline(cin,s);
		N = s.size();

		int ind=0;
		str[0] = s;
		for(ind =1;ind<N;ind++)
		{
			getline(cin,s);
			str[ind]=s;
		}
		//N = str[0].size();
		mx = 0;
		for(int i=0;i<ind;i++)
		{
			for(int j=i;j<ind;j++)
			{
				m = kaadanealgo(i,j);
				if(m>mx)
				mx = m;
			}
		}

		cout<<mx<<"\n";
		if(t)
		cout<<"\n";
	}

	return 0;
}

Similar problems are : uva 108, uva 10074,uva 10667; These can be solved using the same algorithm.