绍兴网站建设方案报价,海外seo推广公司,紫色的网站,奉贤网站制作题目: 返回一个二维整数数组中最大联通子数组的和。 要求#xff1a; 1. 输入一个二维整形数组#xff0c;数组里有正数也有负数。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 2.程序要使用的数组放在一个叫 input.txt 的文件中#xff0c; 文件格式是: 数组的行…题目: 返回一个二维整数数组中最大联通子数组的和。 要求 1. 输入一个二维整形数组数组里有正数也有负数。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 2.程序要使用的数组放在一个叫 input.txt 的文件中 文件格式是: 数组的行数, 数组的列数, 每一行的元素 (用逗号分开) 每一个数字都是有符号32位整数当然行数和列数都是正整数。 代码 #includeiostream
#includefstream
using namespace std;
/*
//求一维数组子数组和的最大值
*/
int getMax(int j,int *array,int first,int last,int col)//first、last为起始元素和最终元素位置
{int sum 0, max 0;int a[100];for (j 0; j col; j){sum sum array[j];a[j] sum;if (sum 0)//和为正数时{sum 0;}if (sum max){max sum;if (max 0)//和为负数时{sum sum array[j];if (sum max){max sum;}}}if (a[j - 1] 0 ){first j;}if (a[j] max){last j;}}return max;
}int main()
{int i, j,map[100][100];int array[100];int max_row[100];int M[100];int max 0;int first_num0;int last_num0;int row,col;ifstream infile(input.txt,ios::in);if(!infile){cerropen error!endl;exit(1);}infile row;infile col;for(i 0; i row; i){for(j 0; j col;j){infile map[i][j];}}cout arrayendl;for (i 0; i row; i){for (j 0; j col; j){cout map[i][j] ;}cout endl;}cout endl;for (i 0; i row; i){for (j 0; j col; j){array[j] map[i][j];}max_row[i]getMax(j, array,first_num,last_num,col);//求每一行的子数组和的最大值cout max_row[i] endl;//每行最大元素cout first element first_num 1 endl;cout last element last_num 1 endl;}for (i 0; i row; i){if (map[i][last_num] map[i 1][first_num] || map[i][first_num] map[i1][last_num]){M[i] max_row[i] max_row[i1];if (M[i] max){max M[i];}}}cout sum of max connected array: max;return 0;
} 我的结队开发队友 信1301-1 刘伟 转载于:https://www.cnblogs.com/xiaoxt/p/5351333.html
