求最大子數組03

題目:

? ? 返回一個二維整數數組中最大聯通子數組的和。

?

要求：

? ?1. 輸入一個二維整形數組，數組里有正數也有負數。 求所有子數組的和的最大值。要求時間復雜度為O(n)。? ??

? ?2.程序要使用的數組放在一個叫 input.txt 的文件中， 文件格式是: 數組的行數, 數組的列數, 每一行的元素， (用逗號分開) 每一個數字都是有符號32位整數，當然，行數和列數都是正整數。

?

代碼：

#include<iostream>
#include<fstream>
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_num=0;int last_num=0;int row,col;ifstream infile("input.txt",ios::in);if(!infile){cerr<<"open 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 << "array："<<endl;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[i+1][last_num]){M[i] = max_row[i] + max_row[i+1];if (M[i] > max){max = M[i];}}}cout << "sum of max connected array:" << max;return 0;
}

?

我的結隊開發隊友 信1301-1 劉偉