CareerCup

<pre lang="" line="1" title="CodeMonkey32219" class="run-this">void find(int b[][4],int m,int n)
{
int i,j,i1,j1,i2,j2,i3,j3;
int c[2][2],sum1,sum2;
sum1=sum2=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
i1=i,j1=j;
while(i1<m)
{

i2=i;
j2=j;
sum1=0;
while(1)
{
if(j2==n||j2>j1)
{ j2=j;
i2++;
}
sum1=sum1+b[i2][j2];
j2++;
if(i2==i1&&j2>j1)
break;
}
if(sum1>sum2)
{
c[0][0]=i;
c[0][1]=j;
c[1][0]=i1;
c[1][1]=j1;
sum2=sum1;

}
j1++;
sum1=0;
if(j1==n)
{
j1=j;
i1++;
}
}
}
}
for(i3=c[0][0];i3<=c[1][0];i3++)
{
for(j3=c[0][1];j3<=c[1][1];j3++)
cout<<" "<<b[i3][j3];
cout<<"\n";
}
cout<<" sum:"<<sum2<<"\n";

}</pre><pre title="CodeMonkey32219" input="yes">
</pre>

#include <stdio.h>
#define ROW 4
#define COL 5

void findMaxSumSubset(int *temp,int *x1,int *x2,int *sum_till_now)
{
	int i,j,max_sum=0;
	
	for(i=0;i<ROW;i++)
	{
		(*sum_till_now)+=temp[i];
		if((*sum_till_now)<=0)
		{
			*sum_till_now=0;
			*x1=i+1;
		}
		
		if((*sum_till_now)>max_sum)
		{
			max_sum=*sum_till_now;
			*x2=i;
		}
	}
	*sum_till_now=max_sum;
}

void display(int (*arr)[COL],int x1,int y1,int x2,int y2)
{
	int i,j;
	printf("\n--------------------------------\n");
	printf("%d %d %d %d\n",x1,y1,x2,y2);
	printf("\n--------------------------------\n");
	for(i=y1;i<=y2;i++)
	{
		for(j=x1;j<=x2;j++)
			printf("%d  ",arr[i][j]);
		printf("\n");
	}
}

void findMaxSumSubsetRectangle(int (*arr)[COL])
{
	int i,j,k,x1,x2,fx1,fx2,fy1,fy2,sum_till_now,max_sum,temp[ROW];
	
	max_sum=0;
	for(i=0;i<COL;i++)
	{
		for(k=0;k<ROW;k++)
			temp[k]=0;
		x1=i;
			
		for(j=i;j<COL;j++)
		{
			sum_till_now=0;
			for(k=0;k<ROW;k++)
				temp[k]+=arr[k][j];
				
			findMaxSumSubset(temp,&x1,&x2,&sum_till_now);
			
			if(sum_till_now>max_sum)
			{
				fy1=x1;
				fy2=x2;
				fx1=i;
				fx2=j;
				max_sum=sum_till_now;
			}
		}
	}
	printf("Max Sum = %d\n",max_sum);
	display(arr,fx1,fy1,fx2,fy2);
	
}

int main()
{
	int arr[ROW][COL],i,j;
	
	for(i=0;i<ROW;i++)
		for(j=0;j<COL;j++)
			scanf("%d",&arr[i][j]);
	
	findMaxSumSubsetRectangle(arr);
	
	return 0;
}

/************************************  SAMPLE OUTPUT  ****************************

1 2 -1 4 -20
8  -3  4  2  1  
3  8  10  -8  3  
-4  -1  1  7  6  
Max Sum = 37

--------------------------------
0 1 4 3
--------------------------------
8  -3  4  2  1  
3  8  10  -8  3  
-4  -1  1  7  6  

*/

if the question is maximum sum of contigous sub array for given array ,
the following is the code ..

// calculated only positive max sum ..

// MaxSubArray.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<conio.h>


int _tmain(int argc, _TCHAR* argv[])
{

#if 1
int arr[13]={-11,-2,6,4,5,10,7,-9,11,15,16,-5,-8};
int first_start =0, first_last =0, current_first=0,current_last =0, first_sum=0,current_sum=0,max_sum=0;
for(int i=0;i<13;i++)
{
if(arr[i]>0)
{
if(i>0)
{

if(arr[i-1]<0)
{
current_first=i;
current_last=i;
current_sum=arr[i];
}
else
{
current_last=i;
current_sum=current_sum+arr[i];

}
if(current_sum >first_sum)
{
first_start=current_first;
first_last=current_last;
first_sum=current_sum;
}
}
else
{

current_first = current_last = first_last = first_start = 0;
first_sum= current_sum =arr[0];

}

}

}
#endif
return 0;
}

#include<stdio.h>

int main()
{
int arr[13]={-11,-2,6,4,5,10,7,-9,11,15,16,-5,-8};
int previous_sum=0;
int current_sum=0;
int i=0;
for(i=0;i<13;i++)
{
if(arr[i]<0)
{
if(previous_sum<=current_sum)
previous_sum=current_sum;
current_sum=0;
}
else
{

current_sum=current_sum+arr[i];

}

}
if(previous_sum>=current_sum)
{

current_sum=previous_sum;
}
printf("Value is %d\n",current_sum);
}

can we solve tbis using dynamic programming?

USE kadanes algorithm for maximum subarray :
en.wikipedia.org/wiki/Maximum_subarray_problem


For extending this problem in 2d for squares the following DP solution can work:
M[ i ][ j ] = min( M[ i -1 ][ j ], M[ i ][ j-1 ],M[ i-1 ][ j-1 ] )+1
where M[ i ][ j ] contains the maximum 2d subarray in size which the original matrix element C[ i ][ j ] is a part of.

USE kadanes algorithm for maximum subarray :
en.wikipedia.org/wiki/Maximum_subarray_problem


For extending this problem in 2d for squares the following DP solution can work:
M[ i ][ j ] = min( M[ i -1 ][ j ], M[ i ][ j-1 ],M[ i-1 ][ j-1 ] )+1
where M[ i ][ j ] contains the maximum 2d subarray in size which the original matrix element C[ i ][ j ] is a part of.

Here is the working Code for 2 dimensional array extending Kanade's Algorithm

#include<stdio.h>
#include<limits.h>
#define M 4
#define N 4

int modify(int arr[M][N])
{
	int i,j;
	for(i=1;i<M;i++)
	for(j=0;j<N;j++)
	arr[i][j]+=arr[i-1][j];
}

int getmaxsum(int arr[M][N])
{
	int i,j,k;
	int max=INT_MIN;
	for(k=1;k<=M;k++)	//taken k 1D arrays at a time
		{
		
		for(i=k-1;i<M;i++)
			{
			int sum=0;
			for(j=0;j<N;j++)
				{
				if(sum>=0)		
					{
					int t=i-k;
					if(t<0)
					sum+=arr[i][j];
					else					
					sum+=arr[i][j]-arr[t][j];
					}
				else
					{
					int t=i-k;
					if(t<0)
					sum=arr[i][j];
					else					
					sum=arr[i][j]-arr[t][j];

					}
				if(sum>max)
				max=sum;
				   }
				}
			}

		
				
return max;

}




int main()
{
int arr[M][N]={
		{1,2,3,-50},
		{1,17,20,10},
		{2,3,4,5},
		{1,19,20,20}
		};


	modify(arr);
	printf("%d",getmaxsum(arr) );	


	return 0;
}