**Problem Statement**: UVA – 108 – Maximum Sum**Submission**:-**Java**–**O ( n^3 )**–**Accepted**

**Difficulty :-****Medium****Type :-**Dynamic , Kadane maximum contiguous Subsequence sum, prefix sum.**Time for Submission :-**3 hours.**Pre-requisites**:-**Solution Description**:-- Imagine that the solution is a sub-matrix from the original one described with a starting row with index
**i**and the matrix width is**w**and composed of certain columns sub-indexed with**c_j**. - Imagine also that every column is the Prefix Sum of the original column.
- so We want to find
- the
**w**which represents the width of the array and we are going to find that with the first loook 7a3adel el 7agat deh kmanp by trying all possible widths. - the starting index
**i**of the row in the second loop.

- the
- we will transform the problem from now into a Kadane problem in which its array is descried by the vector
**< a0, a1 .. an >**where**a_j**is the sum of the elements from the original array in column**j.**

- instead of looping in this column from row index
**i**to row**i + w**we use the prefix sum array to compute it in**O ( 1 )** - After imagining the vector
**<c_0 , c_1 .. c_n >**use this vector as an input to the Kardane Algorithm and it will find for you the maximum contiguous sub-sequence of this vector. - After joining those contiguous sub-columns together we get the wanted sub matrix with the maximum sum.

- Imagine that the solution is a sub-matrix from the original one described with a starting row with index
**Problem :-**- I spent long time to imagine the transformation of the problem into a Kardane problem in the two dimensions. I should have drawn it and didn’t put much time in trying to realize it in my mind only.

- I spent long time to imagine the transformation of the problem into a Kardane problem in the two dimensions. I should have drawn it and didn’t put much time in trying to realize it in my mind only.
**Code :-**

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int N = in.nextInt(); int[][] a = new int[N + 1][N + 1]; for (int i = 1; i <= N; i++) for (int j = 0; j < N; j++) a[i][j] = in.nextInt() + a[i - 1][j]; System.out.println(maxSum(a, N)); } } static long maxSum(int[][] colPrefix, int N) { int KadaneSum = 0, colSum, i, j, w, max = Integer.MIN_VALUE; for (w = 1; w <= N; w++) for (i = 0; i <= N - w; i++, KadaneSum = 0) for (j = 0; j < N; j++) { colSum = colPrefix[i + w][j] - colPrefix[i][j]; KadaneSum = ((KadaneSum >= 0) ? KadaneSum : 0) + colSum; max = KadaneSum > max ? KadaneSum : max; } return max; } }

- Notes:-
- The original problem doesn’t allow negative sums that’s why I used this line in the code

KadaneSum = ((KadaneSum >= 0) ? KadaneSum : 0) + colSum;

Advertisements