子矩阵最大累加和

给定一个矩阵matrix，其中的值有正、有负、有0，返回子矩阵的最大累加和。

蓝桥备战资料《算法很美》Chapter4——多维数组和矩阵

先想到了一维数组的求子数组最大累加和的题目，时间复杂度为O(n)，利用这种思维来处理这道题目。
第一行：-1 -1 -1，最大累加和为-1
第一行+第二行：-2 1 1，最大累加和为2
第一行+第二行+第三行：-3 0 0，最大累加和为0
第二行：-1 2 2，最大累加和为4
第二行+第三行：-2 1 1，最大累加和为2
第三行：-1 -1 -1，最大累加和为-1

这样一来就可以知道子矩阵的最大累加和为4。
需要用到双重循环遍历行的组合，然后利用使用一次一维数组的最大累加和，因此时间复杂度为O(n³)。

#include<iostream>
#include<climits>
using namespace std;

int **arr;

// 一维数组最大子数组累加和
int maxSum(int *arr, int n){
	int s = INT_MIN;
	int tempS = 0;
	for(int i = 0; i < n; i++){
		tempS += arr[i];
		if(tempS > s){
			s = tempS;
		}
		if(tempS < 0){
			tempS = 0;
		}
	}
	return s;
}

// 子矩阵最大累加和 
int maxSum(int **arr, int n){
	int s = INT_MIN;
	int tempS = 0;
	// 从第一行到最后一行
	for(int i = 0; i < n; i++){
		// tempSum为第i行到第j行之间各列之和 
		int *tempSum = new int[n]; 
		for(int j = 0; j < n; j++){
			tempSum[j] = 0;
		}
		// i和j一起确定子矩阵的宽度 
		for(int j = i; j < n; j++){
			// tempSum保存各列的和 
			for(int k = 0; k < n; k++){
				tempSum[k] += arr[j][k];
			}
			// 调用一维数组的求最大累加和方法 
			tempS = maxSum(tempSum, n);
			if(tempS > s){
				s = tempS;
			}
		}
		delete(tempSum); 
	} 
	return s;
}

int main(){
	int n;
	while(cin >> n){
		// 动态创建二维数组 
		arr = new int*[n];
		for(int i = 0; i < n; i++){
			arr[i] = new int[n];
		}
		// 输入数据 
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> arr[i][j];
			}
		}
		// 查找子矩阵最大累加和
		cout << maxSum(arr, n) << endl;
		// 释放数组资源
		for(int i = 0; i < n; i++){
			delete(arr[i]);
		} 
		delete(arr);
	}
	return 0;
}