Kadane’s Algorithm – Live with passion

507

Asif NaeemJuly 16, 2015

#include <iostream>
#include <cstdio>

using namespace std;

int arr[25000];
struct path{
	int len,st,en;
};
path p;
int kadanesAlgo(int rd,int first)
{
	int max_end_here=0,max_so_far=0;
	int begin=first,length;
	int finish=0,start=first;
	for(int i=first;i<rd;i++)
	{
		max_end_here+=arr[i];
		if(max_end_here<0)
		{
			max_end_here=0;
			begin=i+1;
		}
		if(max_end_here>max_so_far)
		{
			max_so_far = max_end_here;
			start=begin;
			finish=i+1;
			length=finish-start+1;

			p.len=length;
			p.en=finish;
			p.st=start;
		}
		else if(max_end_here==max_so_far)
		{
			max_so_far = max_end_here;
			start=begin;
			finish=i+1;
			length=finish-start+1;
			if(length>p.len)
			{
				p.len=length;
				p.en=finish;
				p.st=start;
			}
			else if(length==p.len)
			{
				if(p.st>begin)
				{
					p.st=begin;p.en=finish;
				}
			}
		}
	}
	return max_so_far;
}

int main()
{
	int t,kase=1;
	int rd,res;
	int first;
	cin>>t;
	bool f=0;
	while(t--)
	{
		cin>>rd;
		f=0;
		for(int i=1;i<rd;i++)
		{
			cin>>arr[i];
			if(!f)
			{
				if(arr[i]>0)
				{
					first=i;
					f=1;
				}
			}
		}
		p.en=0;p.st=0;p.len=-1;
		res = kadanesAlgo(rd,first);
		if(res)
		cout<<"The nicest part of route "<<kase++<<" is between stops "<<p.st<<" and "<<p.en<<"\n";
		else
		cout<<"Route "<<kase++<<" has no nice parts\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int arr[25000];

struct path{

int len,st,en;

};

path p;

int kadanesAlgo(int rd,int first)

{

int max_end_here=0,max_so_far=0;

int begin=first,length;

int finish=0,start=first;

for(int i=first;i<rd;i++)

{

max_end_here+=arr[i];

if(max_end_here<0)

{

max_end_here=0;

begin=i+1;

}

if(max_end_here>max_so_far)

{

max_so_far = max_end_here;

start=begin;

finish=i+1;

length=finish-start+1;

p.len=length;

p.en=finish;

p.st=start;

}

else if(max_end_here==max_so_far)

{

max_so_far = max_end_here;

start=begin;

finish=i+1;

length=finish-start+1;

if(length>p.len)

{

p.len=length;

p.en=finish;

p.st=start;

}

else if(length==p.len)

{

if(p.st>begin)

{

p.st=begin;p.en=finish;

}

return max_so_far;

}

int main()

{

int t,kase=1;

int rd,res;

int first;

cin>>t;

bool f=0;

while(t--)

{

cin>>rd;

f=0;

for(int i=1;i<rd;i++)

{

cin>>arr[i];

if(!f)

{

if(arr[i]>0)

{

first=i;

f=1;

}

p.en=0;p.st=0;p.len=-1;

res = kadanesAlgo(rd,first);

if(res)

cout<<"The nicest part of route "<<kase++<<" is between stops "<<p.st<<" and "<<p.en<<"\n";

else

cout<<"Route "<<kase++<<" has no nice parts\n";

}

return 0;

}

10667

Asif NaeemFebruary 7, 2015

#include <iostream>

using namespace std;

int arr[105][105];
int s;

int Matsum(int a,int b)
{
    int p;
    int Line[105];
    int max_end_here,max_so_far;
    for(int i=1;i<=s;i++)
    {
        p=0;
        for(int j=a;j<=b;j++)
        {
           p+=arr[j][i];
        }
        Line[i]=p;
    }

    max_end_here=0;
    max_so_far=0;
    for(int i=1;i<=s;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,mx,m;
    int b,r1,r2,c1,c2;

    cin>>t;

    while(t--)
    {
       cin>>s;
       cin>>b;

       mx =0;
       for(int i=0;i<=101;i++)
        for(int j=0;j<=101;j++)
           arr[i][j]=1;
       while(b--)
       {
         cin>>r1>>c1>>r2>>c2;

         for(int i=r1;i<=r2;i++)
         {
             for(int j=c1;j<=c2;j++)
              arr[i][j]=-10000000;
         }
       }

       for(int i=1;i<=s;i++)
          for(int j=1;j<=s;j++)
          {
             m = Matsum(i,j);
             if(mx<m)
             mx=m;
          }
       cout<<mx<<"\n";
    }

    return 0;
}

#include <iostream>

using namespace std;

int arr[105][105];

int s;

int Matsum(int a,int b)

{

int p;

int Line[105];

int max_end_here,max_so_far;

for(int i=1;i<=s;i++)

{

p=0;

for(int j=a;j<=b;j++)

{

p+=arr[j][i];

}

Line[i]=p;

}

max_end_here=0;

max_so_far=0;

for(int i=1;i<=s;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,mx,m;

int b,r1,r2,c1,c2;

cin>>t;

while(t--)

{

cin>>s;

cin>>b;

mx =0;

for(int i=0;i<=101;i++)

for(int j=0;j<=101;j++)

arr[i][j]=1;

while(b--)

{

cin>>r1>>c1>>r2>>c2;

for(int i=r1;i<=r2;i++)

{

for(int j=c1;j<=c2;j++)

arr[i][j]=-10000000;

}

for(int i=1;i<=s;i++)

for(int j=1;j<=s;j++)

{

m = Matsum(i,j);

if(mx<m)

mx=m;

}

cout<<mx<<"\n";

}

return 0;

}

10074

Asif NaeemFebruary 7, 2015

#include <iostream>

using namespace std;

int arr[105][105];
int M,N;

int Matsum(int a,int b)
{
    int p,max_end_here=0,max_so_far=0;
    int Line[105];
    for(int i=1;i<=N;i++)
    {
       p = 0;
       for(int j=a;j<=b;j++)
       {
           p+=arr[j][i];
       }
       Line[i]=p;
    }

    max_end_here=0;
    max_so_far=0;
    for(int i=1;i<=N;i++)
    {
       max_end_here = max_end_here + Line[i];

       if(max_end_here<0)
          max_end_here = 0;
       if(max_so_far<max_end_here)
         max_so_far = max_end_here;

    }

    return max_so_far;
}

int main()
{
    int a;
    int mx=0,x;
    while(cin>>M>>N)
    {
       if(M==0 && N==0)
       break;
       for(int i=1;i<=M;i++)
       {
          for(int j=1;j<=N;j++)
          {
             cin>>a;
             if(a==0)
             arr[i][j]=1;
             //a = -1;
             if(a)
             arr[i][j]=-1000000;//a[i-1][j]+a;
          }
       }
       mx = 0;
       for(int i=1;i<=M;i++)
       {
           for(int j=i;j<=M;j++)
           {
              x = Matsum(i,j);
              if(x>mx)
              mx=x;
           }
       }

       cout<<mx<<"\n";
    }//end while

    return 0;
}

#include <iostream>

using namespace std;

int arr[105][105];

int M,N;

int Matsum(int a,int b)

{

int p,max_end_here=0,max_so_far=0;

int Line[105];

for(int i=1;i<=N;i++)

{

p = 0;

for(int j=a;j<=b;j++)

{

p+=arr[j][i];

}

Line[i]=p;

}

max_end_here=0;

max_so_far=0;

for(int i=1;i<=N;i++)

{

max_end_here = max_end_here + Line[i];

if(max_end_here<0)

max_end_here = 0;

if(max_so_far<max_end_here)

max_so_far = max_end_here;

}

return max_so_far;

}

int main()

{

int a;

int mx=0,x;

while(cin>>M>>N)

{

if(M==0 && N==0)

break;

for(int i=1;i<=M;i++)

{

for(int j=1;j<=N;j++)

{

cin>>a;

if(a==0)

arr[i][j]=1;

//a = -1;

if(a)

arr[i][j]=-1000000;//a[i-1][j]+a;

}

mx = 0;

for(int i=1;i<=M;i++)

{

for(int j=i;j<=M;j++)

{

x = Matsum(i,j);

if(x>mx)

mx=x;

}

cout<<mx<<"\n";

}//end while

return 0;

}

108

Asif NaeemFebruary 7, 2015

#include <stdio.h>

int a[100][100]={0};
int N;
int Line[100];

int KadaneAlg();
int MatSum(int a,int b);

int main()
{
	int p=-100;
	int Max=-100;
	while(scanf("%d",&N)==1)
	{
		Max=-100;
		p =-100;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
				scanf("%d",&a[i][j]);
		}

		for(int k=0;k<N;k++)
		{
			for(int l=k;l<N;l++)
			{
				p = MatSum(k,l);
				if(p>Max)
					Max = p;
			}
		}

		printf("%d\n",Max);
	}

	return 0;
}


int MatSum(int c,int b)
{
	int p;
	for(int i=0;i<N;i++)
	{
		p =0;
		for(int j=c;j<=b;j++)//row
		{
			p += a[j][i];
		}
		Line[i] = p;
	}

	return KadaneAlg();

}

int KadaneAlg()
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < N; i++)
   {
     max_ending_here = max_ending_here + Line[i];
     if(max_ending_here < 0)
         max_ending_here = 0;
     else if (max_so_far < max_ending_here)
         max_so_far = max_ending_here;
   }
   return max_so_far;
}

#include <stdio.h>

int a[100][100]={0};

int N;

int Line[100];

int KadaneAlg();

int MatSum(int a,int b);

int main()

{

int p=-100;

int Max=-100;

while(scanf("%d",&N)==1)

{

Max=-100;

p =-100;

for(int i=0;i<N;i++)

{

for(int j=0;j<N;j++)

scanf("%d",&a[i][j]);

}

for(int k=0;k<N;k++)

{

for(int l=k;l<N;l++)

{

p = MatSum(k,l);

if(p>Max)

Max = p;

}

printf("%d\n",Max);

}

return 0;

}

int MatSum(int c,int b)

{

int p;

for(int i=0;i<N;i++)

{

p =0;

for(int j=c;j<=b;j++)//row

{

p += a[j][i];

}

Line[i] = p;

}

return KadaneAlg();

}

int KadaneAlg()

{

int max_so_far = 0, max_ending_here = 0;

int i;

for(i = 0; i < N; i++)

{

max_ending_here = max_ending_here + Line[i];

if(max_ending_here < 0)

max_ending_here = 0;

else if (max_so_far < max_ending_here)

max_so_far = max_ending_here;

}

return max_so_far;

}

836

Asif NaeemFebruary 7, 2015

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;
}

#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);

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.

Category: Kadane’s Algorithm

507

10667

10074

108

836

Archives

Categories