Cod sursa(job #1178774)

Utilizator Gusti666Lucaciu Catalin Gusti666 Data 27 aprilie 2014 11:15:34
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
using namespace std;
int n,A[101][101],S[101][101];
int i,j,rez;
int lst,cst,ldr,cdr;
int suma;
int main()
{
	cin>>n;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			cin>>A[i][j];
			S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j];
		}
	rez=-1000000000;
	for (lst=1;lst<=n;lst++)
		for (cst=1;cst<=n;cst++)
			for (ldr=lst;ldr<=n;ldr++)
				for (cdr=cst;cdr<=n;cdr++)
				{
					suma=S[ldr][cdr]-S[lst-1][cdr]-S[ldr][cst-1]+S[lst-1][cst-1];
					if (suma>rez)
						rez=suma;
				}
	cout<<rez;	
	return 0;
}