uva 108 - Maximum Sum - Solution using Kadane Algorithm

uva 108 - Maximum Sum - Solution using Kadane Algorithm

#include<iostream>
#include<algorithm>

using namespace std;

void kadane_algo(int *arr, int len, int &max_value){
if (len == 0)
return;
int tempSum  = arr[0];
if (tempSum > max_value)
max_value = tempSum;
for (int i = 1; i < len; i++){
if (tempSum < 0){
if (max_value <= arr[i]){
tempSum = max_value = arr[i];
}
else{
tempSum += arr[i];
if (tempSum < arr[i])
tempSum = arr[i];
}
}
else{
tempSum += arr[i];
if (tempSum < arr[i])
tempSum = arr[i];
if (tempSum > max_value){
max_value = tempSum;
}
}
}
}

void calculate_max_2d_rect_sum(int arr[][100], int row,int &max_value){
int temp[100], i, j, k, temp_max_value;
max_value=temp_max_value = arr[0][0];
for (i = 0; i < row; i++){
fill(temp, temp + row, 0);
for (j = i; j < row; j++){
for (k = 0; k < row; k++){
temp[k] += arr[j][k];
}
kadane_algo(temp, row, max_value);
if (temp_max_value < max_value){
temp_max_value = max_value;
}
}
}
}

int main(){
int n, arr[100][100], i, j,max_value;
while (cin >> n){
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> arr[i][j];
calculate_max_2d_rect_sum(arr, n, max_value);
cout << max_value << endl;
}
return 0;
}