UVa 108

From Algorithmist

Contents 1 108 - Maximum Sum 2 Summary 3 Explanation 4 Notes 5 Input 6 Output

[edit] 108 - Maximum Sum

• http://online-judge.uva.es/p/v1/108.html

[edit] Summary

Given an n by n two-dimensional array arr (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.

[edit] Explanation

• First, calculate the vertical prefix sum for all columns (an O(n²) algorithm).
• Second, assume that the maximum sub-array will be between row a and row b, inclusive. There are only O(n²) a, b pairs such that a < b. Try each of them.
• Since we already have the vertical prefix sum for all columns, the sum of elements in arr[a..b][c] for column c can be computed in 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 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 O(n³).

[edit] Notes

An O(n⁴) algorithm can get an AC on UVa Online Judge. But anything above that won't.

[edit] 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

[edit] Output

-1
18589
15