10684 – The jackpot

A 1D array maximum sub-array problem.
The solution is Dynamic Programming. This maximum sub-array technique is also known as Kadane’s Algorithm.
C++ implementation:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	long n, e, sum, maxSum;
	while (cin >> n && n) {
		sum = maxSum = 0;
		while (n--) {
			cin >> e;
			sum += e;
			if (sum < 0)
				sum = 0;
			maxSum = max(maxSum, sum);
		}
		if (maxSum > 0)
			cout << "The maximum winning streak is " << maxSum << ".";
		else
			cout << "Losing streak.";
		cout << endl;
	}
	return 0;
}

108 – Maximum Sum

A maximum submatrix problem. A brute-force solution wouldn’t get TLE. My C rank-4624 implementation:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX(X, Y) (X > Y) ? X : Y
#define MIN(X, Y) (X < Y) ? X : Y

#define N 101

int array[N][N], n;

int main() {
	int x, y, x2, y2, val, max = INT_MIN;
	scanf("%d", &n);
	for (y = 0; y < n; ++y) {
		for (x = 0; x < n; ++x) {
			scanf("%d", &val);
			array[y][x] = val;
			if (x > 0)
				array[y][x] += array[y][x - 1];
			if (y > 0)
				array[y][x] += array[y - 1][x];
			if (y > 0 && x > 0)
				array[y][x] -= array[y - 1][x - 1];
			max = MAX(max, array[y][x]);
		}
	}

	for (y = 0; y < n; ++y) {
		for (x = 0; x < n; ++x) {

			for (y2 = y; y2 < n; ++y2) {
				for (x2 = x; x2 < n; ++x2) {
					max = MAX(max, array[y2][x2] - array[y2][x] - array[y][x2] + array[y][x]);
				}
			}

		}
	}
	printf("%d\n", max);
	return 0;
}

Another solution is done via Kadane’s Algorithm which is DP. This is what’s acutually required by the problem setter. With Kadane’s Algorithm able to solve a 1D/array problem, we need to reduce the 2D/matrix problem at hand to a 1D problem.

• As you might have guessed, this reduction is easily made with prefix/cumulative sum. We simply add the value of each row to all the following ones. This is done simultaneously along taking input.
• Combine each two rows and do the Kadane algorithm.
• Done!

My C implementation:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX(X, Y) (X > Y) ? X : Y
#define POS(X) MAX(X, 0)

#define N 101

int matrix[N][N], n, maxSum = INT_MIN;

int kadane(int* row, int len) {
	int x, sum;
	for (x = 0, sum = POS(row[0]); x < len; ++x, sum = POS(sum + row[x]))
		maxSum = MAX(sum, maxSum);
	return maxSum;
}

int kadane2(int* row1, int* row2, int len) {
	int x, sum;
	for (x = 0, sum = POS(row2[0] - row1[0]); x < len; ++x, sum = POS(sum + row2[x] - row1[x]))
		maxSum = MAX(sum, maxSum);
	return maxSum;
}

int main() {
	int x, y, y2;
	/*input*/
	scanf("%d", &n);
	for (x = 0; x < n; ++x)
		scanf("%d", &matrix[0][x]);
	for (y = 1; y < n; ++y) {
		for (x = 0; x < n; ++x) {
			scanf("%d", &matrix[y][x]);
			matrix[y][x] += matrix[y - 1][x];
		}
	}
	/*solve*/
	for (y = 0; y < n; ++y) {
		kadane(matrix[y], n);
		for (y2 = y + 1; y2 < n; ++y2)
			kadane2(matrix[y], matrix[y2], n);
	}
	/*result*/
	printf("%d\n", maxSum);
	return 0;
}

Rank 253. Worth it?

Maximum Subarray – Kadane

A You’re given an integer array of length n and your required to compute the sum of a k contiguous elements that have the maximum sum.
A brute force solution would be . So we present Kadane’s algorithm which solves the problem in an slick subrotine.
The idea is simple. First, take a look at the pseudo-code:

KADANE(array, len)
	sum = 0
	maxSum = -
	for x = 0 to len
		sum += array[x]
		maxSum = MAX(sum, maxSum)
		if(sum < 0)
			sum = 0
	return maxSum

We keep adding up elements until the sum changes sign, then, we reset the sum.
The algorithm has a key observation, that whenever a contiguous chunk of the array gives negative sum, it’s no longer of use:

• Adding up more elements to this chunk is not a good choice. We’d better take these new elements in a new chunk so that we could benefit most from them
• There’s some “barrier” that made this chunk change sign — a very large negative element(s) at which we reset sum –. No maximum subarray would be crossing that barrier.

Why is this a Dynamic Programming algorithm?
The maximum subarray ending at each position is calculated from a related but smaller subproblem which is the maximum subarray ending at the previous position.

An implementation in C++:

#include <iostream>
#include <climits>
using namespace std;

#define MAX(X, Y) (X > Y) ? X : Y
#define POS(X) (X > 0) ? X : 0

#define N 11

int arr[N] = { 1, -6, 2, -1, 4, -1, 2, 1 };

int maxSum = INT_MIN;

int kadane(int* row, int len) {
	int x, sum, maxSum = INT_MIN;
	for (sum = POS(row[0]), x = 0; x < N; ++x, sum = POS(sum + row[x]))
		maxSum = MAX(sum, maxSum);
	return maxSum;
}

int main() {
	cout << kadane(arr, N) << endl;
	return 0;
}