# UVa 108

## 108 - Maximum Sum

Quite similar to 10074 and 10667.

## Summary

Given an n by n two-dimensional array arr (${\displaystyle 1<=n<=100}$) of arbitrary integers, find the maximum sub-array. Maximum sub-array is defined to be the sub-array whose sum of integer elements are the maximum possible.

## Explanation

• First, calculate the vertical prefix sum (cumulative sum) for all columns (an ${\displaystyle O(n^{2})}$ algorithm).
• Second, assume that the maximum sub-array will be between row a and row b, inclusive. There are only ${\displaystyle O(n^{2})}$ a, b pairs such that ${\displaystyle a. Try each of them.
• Since we already have the vertical prefix sum for all columns, the sum of elements in ${\displaystyle arr[a..b][c]}$ for column c can be computed in ${\displaystyle O(1)}$ time. This allows us to imagine each column sum as if it is a single element of a one-dimensional array across all columns (one dimensional array with one row and n columns).
• There's an ${\displaystyle O(n)}$ algorithm to compute the maximum sub-array for a one-dimensional array, known as Kadane's Algorithm.
• Applying the Kadane's algorithm inside each a and b combination gives the total complexity of ${\displaystyle O(n^{3})}$.
```/*************************************************
* Amazon Interview Question:                     *
* Problem: Maximum Sum Sub Matrix                *
* Visit: http://programming-puzzles.blogspot.in/ *
* Author : Ramprasad Gopalakrishnan              *
* Language : C++                                 *
**************************************************/

#include<iostream>
#include<list>
#include <algorithm>

using namespace std;

void getNextInputSet();
void printMatrix(int* matrix, int m1, int m2, int n1, int n2);
int maximumSumSubArray(int array[], int size, int* maxStartRetVal, int* maxTailRetVal);

/*
** input Matrix
**/
int inputMatrix[10][10] = {
{2,-1,2,-1,4,-5},
{2,8,2,-1,4,-5},
{2,-1,2,-1,4,-5},
{2,-1,2,-1,4,-5},
{2,-1,2,-1,4,-5},
{-2,-1,-2,-1,4,-5}
};
int m = 6, n = 6;

/*
**sumMatrix:
** sumMatrix[i][j] gives the sum of column j till the ith row.
*/
int sumMatrix[10][10] = {{0}};

int main() {
while(n > 0 && m >0) {

for(int i = 1; i<=m;i++) {
for(int j=0; j<n; j++)  {
sumMatrix[i][j] = sumMatrix[i-1][j] + inputMatrix[i-1][j];
}
}

cout<<"SumMatrix:\n";
printMatrix(*sumMatrix,0,m,0,n-1);

int maxSum = sumMatrix[0][0], maxRowStart = 0, maxRowTail = 0, maxColStart =0, maxColTail = 0;
cout<<"\n\nRij Matrix:\n";
for(int i=0; i<n; i++) {
for(int j=i; j<n; j++) {
/*r_ij matrix.
* k th element in the matrix is the sum of all elements in
* column k from row i to j in inputMatrix.
*/
int r_ij[10] = {0};

cout<<"R"<<i<<","<<j<<": ";
for(int k=0; k<m; k++) {
r_ij[k] = sumMatrix[j+1][k] - sumMatrix[i][k];
cout<<r_ij[k]<<" ";
}
cout<<endl;

int maxStartForRij, maxTailForRij, maxSumRij;

maxSumRij = maximumSumSubArray(r_ij, m, &maxStartForRij, &maxTailForRij);

//update with tne new maxSum
if(maxSumRij>maxSum) {
maxSum = maxSumRij;
maxRowStart = i;
maxRowTail = j;
maxColStart = maxStartForRij;
maxColTail = maxTailForRij;
}
}
}

printMatrix(*inputMatrix,maxRowStart,maxRowTail,maxColStart,maxColTail);

getNextInputSet();
}
}

/**
* This solves the sub problem of maximumSumSubArray.
* i.e. returns the sub array with the maximum sum.
*
*/
int maximumSumSubArray(int array[], int size, int* maxStartRetVal, int* maxTailRetVal) {
int currentStart = 0, maxStart = 0, maxTail =0, currentSum = array[0], maxSum = array[0] ;

for(int currentTail = 1;currentTail < size; currentTail++) {
if(currentSum > 0) {
currentSum += array[currentTail];
} else {
currentStart = currentTail;
currentSum = array[currentTail];
}

if(currentSum > maxSum) {
maxSum = currentSum;
maxTail = currentTail;
maxStart = currentStart;
}
}

*maxStartRetVal = maxStart;
*maxTailRetVal = maxTail;
return maxSum;
}

/*
* Utility functions.
*/
void getNextInputSet() {
//get next set of inputs
cout<<"\n\nEnter M N (0 0 to quit):";
cin>>m>>n;
if(m>0 && n>0) {
for(int i = 0; i<m;i++) {
cout<<"Enter row " << i <<endl;
for(int j=0; j<n; j++)
cin>>inputMatrix[i][j];
}
}
}

void printMatrix(int* matrix, int m1, int m2, int n1, int n2) {
for(int i = 0; i<=m;i++) {
for(int j=0; j<n; j++)  {
cout<<sumMatrix[i][j]<<" ";
}
cout<<endl;
}
}
```

## Notes

An ${\displaystyle O(n^{4})}$ algorithm can get an AC on UVa Online Judge. But anything above that won't.

## Input

```4
-1 -2 -3 -4
-5 -6 -7 -8
-9 -10 -11 -12
-13 -14 -15 -16
5
1 -61 5126 612 6
41 6 7 2 -7
1 73 -62 678 1
7 -616136 61 -83 724
-151 6247 872 2517 8135
4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2
```

[ Be careful! This doesn't seem a valid sample. Problem statement says "The numbers in the array will be in the range [-127, 127]."]

## Output

```-1
18589
15
```

[This algo will return 0 for the first example (a nil matrix) instead of -1]