Adobe Interview Question
Software Engineer / Developers#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
*/
What is all elements are negative??
just change this one!
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)>max_sum)
{
max_sum=*sum_till_now;
*x2=i;
}
if((*sum_till_now)<=0)
{
*sum_till_now=0;
*x1=i+1;
}
}
*sum_till_now=max_sum;
}
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);
}
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;
}
<pre lang="" line="1" title="CodeMonkey32219" class="run-this">void find(int b[][4],int m,int n)
- BIPLOVESARKAR August 25, 2011{
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>