联通子数组最大值设计03

#include<iostream>
using namespace std;

void max_place(int row,int &max,int fl[],int &start,int &end);

int main()
{
	int a[100][100];
	int fl[100];
	int hang=0,lie=0;
	int start_k[100],end_k[100];    //定义二维数组中每一次起始终止位置
	int large[100];
	int max=0;
	int start=0,end=0;    //位置参数
	cout<<"请输入数组行列数:"<<endl;
	cin>>hang>>lie;
	 int i=0,j=0;
	for(i=0;i<hang;i++)
		for(j=0;j<lie;j++)
		{
			cin>>a[i][j];
		}

	 for(i=0;i<hang;i++)
		{
			for(j=0;j<lie;j++)
		{
			cout<<a[i][j]<<" ";
		}
			cout<<endl;
	 }

		//对于数组找到最大联通数组的和
		for(i=0;i<hang;i++)
		{
			
			for(j=0;j<lie;j++)
			{
				fl[j]=a[i][j];
				
			}
			max_place(lie,max,fl,start,end);

			cout<<"开始位置："<<start<<" "<<end<<endl;
			cout<<"最大值为："<<max<<endl;
			start_k[i]=start;
			end_k[i]=end;
			large[i]=max;
		}

		int max2=large[0];
		//找到连同数组的情况：分情况讨论
		for(i=0;i<hang-1;i++)
		{
			//若上下数组行联通
			if((start_k[i+1]<=end_k[i])&&(start_k[i]<=end_k[i+1]))
			{
				max2+=large[i+1];
			}
			//上下不联通考虑最小代价
			//第一行在第二行右边
			if(start_k[i]>=end_k[i+1])
			{
				int p=large[i+1]+large[i];
				int r1=0,r2=0,r=0;
				//两种判断
				for( j=end_k[i+1]+1;j<=start_k[i];j++)
				  r1+=a[i][j];
				for( j=end_k[i+1]+1;j<start_k[i];j++)
				  r2+=a[i][j];

				r2=r2+a[i][end_k[i+1]+1];
				r=r1;
				if(r2>r1)
					r=r2;

				if(p+r>p)
				max2=max2+p+r;
			}
			//第一行在第二行左边
			if(start_k[i+1]>=end_k[i])
			{
				int p=large[i+1]+large[i];
				int r=0;
				for( j=end_k[i]+1;j<start_k[i+1];j++)
				  r+=a[i][j];
				for( j=end_k[i+1]+1;j<start_k[i+1];j++)
				  r+=a[i][j];


				if(p+r>p)   //如果存在更新判断域
				max2=max2+p+r;
			}	
			//单独正数的情况
			for(j=start_k[i];j<start_k[i+1];j++)
			{
				if(a[i+1][j]>0)
					max2+=a[i+1][j];
			}
		}
		cout<<"最大值为"<<max2<<endl;
	return 0;
}

//找到二维数组中每一行最大的值的起始位置
void max_place(int row,int &max,int fl[],int &start,int &end)
{
	//求每个一维数组的最大值
	int b[100]={0},s=0;   //存放最大值
	//finding
	for(int i=0;i<row;i++)
	{
		if(s>=0)
		{
			s+=fl[i];
		}
		else
		{
			s=fl[i];
		}
		b[i]=s;
	}

	//
	int max_num=b[0];
	for(int i=0;i<row;i++)
	{
		if(b[i]>max_num)
		{
			max_num=b[i];
			end=i;     //末位置
		}
	}

	for(int i=end;i>=0;i--)
	{
		if(fl[i] == b[i])
		{
			start=i;    //找到首位置
		   break;
		}
	}
	max=max_num;   //返回最大值
}