UVA – 108 – Maximum Sum

  • Problem Statement : UVA – 108 –  Maximum Sum
  • Submission:-
    • JavaO ( n^3 )Accepted
  • Difficulty :- Medium
  • Type :- Dynamic , Kadane maximum contiguous Subsequence sum, prefix sum.
  • Time for Submission :- 3 hours.
  • Pre-requisites:-
  • Solution Description:-
    1. 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 wand composed of certain columns sub-indexed with  c_j .
    2. Imagine also that every column is the Prefix Sum of the original column.
    3. so We want to find
      1. 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.
      2. the starting index i of the row in the second loop.
    4. 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.
    5. 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 )
    6. 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.
    7. After joining those contiguous sub-columns together we get the wanted sub matrix with the maximum sum.
  • 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.
  • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: