UVA 10755 ( Maximum Sum of a 3D array )

Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1696&mosmsg=Submission+received+with+ID+26247413

Problem Approach: The first prerequisite to solve this problem is Kadane’s algorithm. As we have to find the maximum_sum cube inside the given 3D array. The naive complexity is-

n^9 (n^3 starting positions, n^3 ending positions and for summation n^3).

We can choose take x and y axis value for generating sub-rectangle and apply Kadane’s algorithm on z axis. Thus, the complexity will be equal to- n^2*n^2*n=n^5.

Code:

	#include <bits/stdc++.h>
	#define mxs 100005
	#define ll long long int
	#define print_case printf("Case %lld: ",ts++)
	using namespace std;
	ll arr[100005],n,m,cnt;
	ll qube[21][21][21],cum[21][21][21],sum[21];
	ll kadane(ll c)
	{
	ll i,mx=sum[1],s=0;
	for(i=1;i<=c;i++)
	{
	s+=sum[i];
	mx=max(mx,s);
	s=s<0?0:s;
	}
	return mx;
	}
	ll sum_at(int xs,int xe,int ys,int ye,int i)
	{
	return qube[xe][ye][i]-qube[xe][ys-1][i]-qube[xs-1][ye][i]+qube[xs-1][ys-1][i];
	}
	int main()
	{
	ll t,k,a,b,d,x,y,i,q,j,l,s,c,ans,mx=INT_MIN,mn=INT_MAX,ts=1;
	cin>>t;
	while(t--)
	{
	cin>>a>>b>>c;
	mx=INT_MIN;
	for(i=1;i<=a;i++)
	{
	for(j=1;j<=b;j++)
	{
	for(k=1;k<=c;k++)
	{
	cin>>qube[i][j][k];
	mx=max(mx,qube[i][j][k]);
	qube[i][j][k]+=qube[i-1][j][k]+qube[i][j-1][k]-qube[i-1][j-1][k];
	}
	}
	}
	int xs,xe,ys,ye;
	for(xs=1;xs<=a;xs++)
	{
	for(xe=xs;xe<=a;xe++)
	{
	for(ys=1;ys<=b;ys++)
	{
	for(ye=ys;ye<=b;ye++)
	{
	for(i=1;i<=c;i++)
	{
	sum[i]=sum_at(xs,xe,ys,ye,i);
	}
	mx=max(mx,kadane(c));
	}
	}
	}
	}
	cout<<mx<<endl;
	if(t)
	cout<<endl;
	}
	return 0;
	}
	/*
	2
	2 2 2
	-1 2 0 -3 -2 -1 1 5
	2 2 2
	-1 2 0 -3 -2 -1 1 5
	*/

view raw uva_10755.cpp hosted with ❤ by GitHub