//思路：对n*m的二维数组进行分解，分解为n个一维数组，再先求这n个一维数组的最大子数组和，并记下每行最大一维子数组的下标如2-5，这是就会分两种情况第一种是行之间的最大子数组是相连的，如第一行是2-5，第二行是3-6，这是直接相加就行。第二种是不相连的如第一行是2-5，第二行是6-7，这时候就把每行的最大子数组看成一个整体，再使每个最大数组块进行相连，求使其相连的最小代价。最后就可求出最大联通子数组的和。
#include<iostream>
#include<fstream>
#define N 100
using namespace std;
int zuida(int n, int a[], int *sm, int *mm)
{
int b[100] = { 0 };
int i, sum1 = 0, max1 = 0;
for (i = 0; i<n; i++)
{
if (sum1<0)
{
sum1 = a[i];
}
else
{
sum1 = sum1 + a[i];
}
b[i] = sum1;
}
max1 = b[0];
for (i = 0; i<n; i++)
{
if (max1<b[i])
{
max1 = b[i];
*mm = i;
}
}
for (i = *mm; i >= 0; i--)
{
if (b[i] == a[i])
{
*sm = i;
break;
}
}
return max1;
}
void readarry(int arry[][N], int &line, int &row) //读取txt文件中的二维数组
{
ifstream infile("a.txt");
if (!infile)
cout << "读取失败！" << endl;
else
{
infile >> line >> row;
for (int i = 0; i<line; i++)
{
for (int j = 0; j<row; j++)
{
infile >> arry[i][j];
}
}
}
}
void show(int arry[][N], int line, int row) //显示数组
{
printf("从“a.txt”文件中读取的数组为：
");
for (int i = 0; i<line; i++)
{
for (int j = 0; j<row; j++)
{
printf(" %d ", arry[i][j]);
}
printf("
");
}
}
void main()
{
int line, row, i, j, sm, mm, t2;
int sum, max;
int up[100], down[100], t[100];
int a[100][100], b[100];
readarry(a, line, row);
show(a, line, row);
for (i = 0; i<line; i++)
{
for (j = 0; j<row; j++)
{
b[j] = a[i][j];
}
sum = zuida(row, b, &sm, &mm);
up[i] = sm;
down[i] = mm;
t[i] = sum;
}
t2 = t[0];
for (i = 0; i + 1<line; i++)
{
if (up[i] <= down[i + 1] && down[i] >= up[i + 1])
{
t2 += t[i + 1];
}
for (j = up[i]; j<up[i + 1]; j++)
{
if (a[i + 1][j]>0) t2 += a[i + 1][j]; //判别独立正数
}
}
cout << t2 << endl;
}
