TADM2E 8.21 - Revision history

Matt: Undo revision 960 by Erecua (talk)

2020-07-24T13:13:18Z

Undo revision 960 by Erecua (talk)

Matt: Undo revision 961 by Erecua (talk)

2020-07-24T13:12:52Z

Undo revision 961 by Erecua (talk)

Erecua: Replaced content with " $Fuck you$ "

2020-07-24T12:12:42Z

Replaced content with "<math>Fuck you</math>"

Erecua at 12:12, 24 July 2020

2020-07-24T12:12:04Z

Matt: Undo revision 835 by Ufsuraifs (talk)

2020-07-23T14:45:49Z

Undo revision 835 by Ufsuraifs (talk)

Ufsuraifs: Blanked the page

2020-07-17T02:50:52Z

Blanked the page

LiavK: Minor code formatting fixes. Still looks a little wiggy.

2017-10-20T18:32:26Z

Minor code formatting fixes. Still looks a little wiggy.

LiavK: Removes an incorrect solution and presents what I believe is a correct O(n) solution to the max-range problem, with test cases.

2017-10-20T18:26:46Z

Removes an incorrect solution and presents what I believe is a correct O(n) solution to the max-range problem, with test cases.

Azazel: /* 2 */

2016-12-22T19:38:52Z

‎2

Azazel: Created page with "==== 1 ==== Sum every range and keep track of the maximum. Given a set of numbers N = { x0, x1 ... xn } M = 0 for i in (0 .. n) S[i, i] = xi for j in (i + 1 ....."

2016-12-22T19:32:05Z

Created page with "==== 1 ==== Sum every range and keep track of the maximum. Given a set of numbers N = { x0, x1 ... xn } M = 0 for i in (0 .. n) S[i, i] = xi for j in (i + 1 ....."

New page

==== 1 ====

Sum every range and keep track of the maximum.

Given a set of numbers N = { x0, x1 ... xn }

M = 0

for i in (0 .. n)
S[i, i] = xi
for j in (i + 1 .. n)
S[i, j] = S[i, j - 1] + xj
if M < S[i, j]
M = S[i, j]

==== 2 ====

Sum from each end, resetting the prefix or suffix (i.e., discarding the summed numbers) if it goes negative.

#!/usr/bin/perl

sub max_range
{
my @numbers = @_;

my $prefix = 0;
my $suffix = 0;

for (my ($l, $r) = (0, @numbers - 1); $l <= $r; $l ++, $r --)
{
$prefix += $numbers[$l];
$prefix = 0 if $prefix < 0;

$suffix += $numbers[$r] if $l < $r;
$suffix = 0 if $suffix < 0;
}

return $prefix + $suffix;
}

my $max = max_range 31, -41, 59, 26, -53, 58, 97, -93, -23, 84;

print $max, "\n";

@@ Line 4: / Line 4: @@
   Given a set of numbers N = { x0, x1 ... xn }
-  <math>N = 5</math>
   M = 0

← Older revision		Revision as of 13:12, 24 July 2020
Line 1:		Line 1:
−	<math>~~Fuck you~~</math>	+	==== 1 ====
		+
		+	Sum every range and keep track of the maximum.
		+
		+	Given a set of numbers N = { x0, x1 ... xn }
		+	<math>N = 5</math>
		+	M = 0
		+
		+	for i in (0 .. n)
		+	S[i, i] = xi
		+	for j in (i + 1 .. n)
		+	S[i, j] = S[i, j - 1] + xj
		+	if M < S[i, j]
		+	M = S[i, j]
		+
		+	==== 2 ====
		+
		+	def max_range(items):
		+	max_diff = max(items[0], 0)
		+	temp_diff = 0
		+	for number in items:
		+	temp_diff = max(0, temp_diff + number)
		+	max_diff = max(max_diff, temp_diff)
		+	return max_diff
		+
		+	assert max_range([1, 2, 3, 4, 5]) == 15
		+	assert max_range([-1, -2, -3, -4, -5]) == 0
		+	assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187
		+	assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187
		+	assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51
		+	assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51

← Older revision		Revision as of 12:12, 24 July 2020
Line 1:		Line 1:
−	~~==== 1 ====~~	+	<math>Fuck you</math>
−
−	~~Sum every range and keep track of the maximum.~~
−
−	~~Given a set of numbers N = { x0, x1 ... xn }~~
−	<math>~~N = 5~~</math>
−	~~M = 0~~
−
−	~~for i in (0 .. n)~~
−	~~S[i, i] = xi~~
−	~~for j in (i + 1 .. n)~~
−	~~S[i, j] = S[i, j - 1] + xj~~
−	~~if M < S[i, j]~~
−	~~M = S[i, j]~~
−
−	~~==== 2 ====~~
−
−	~~def max_range(items):~~
−	~~max_diff = max(items[0], 0)~~
−	~~temp_diff = 0~~
−	~~for number in items:~~
−	~~temp_diff = max(0, temp_diff + number)~~
−	~~max_diff = max(max_diff, temp_diff)~~
−	~~return max_diff~~
−
−	~~assert max_range([1, 2, 3, 4, 5]) == 15~~
−	~~assert max_range([-1, -2, -3, -4, -5]) == 0~~
−	~~assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187~~
−	~~assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187~~
−	~~assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51~~
−	~~assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51~~

@@ Line 4: / Line 4: @@
   Given a set of numbers N = { x0, x1 ... xn }
+  <math>N = 5</math>
   M = 0

← Older revision	Revision as of 14:45, 23 July 2020
Line 1:	Line 1:
	+	==== 1 ====

	+	Sum every range and keep track of the maximum.
	+
	+	Given a set of numbers N = { x0, x1 ... xn }
	+
	+	M = 0
	+
	+	for i in (0 .. n)
	+	S[i, i] = xi
	+	for j in (i + 1 .. n)
	+	S[i, j] = S[i, j - 1] + xj
	+	if M < S[i, j]
	+	M = S[i, j]
	+
	+	==== 2 ====
	+
	+	def max_range(items):
	+	max_diff = max(items[0], 0)
	+	temp_diff = 0
	+	for number in items:
	+	temp_diff = max(0, temp_diff + number)
	+	max_diff = max(max_diff, temp_diff)
	+	return max_diff
	+
	+	assert max_range([1, 2, 3, 4, 5]) == 15
	+	assert max_range([-1, -2, -3, -4, -5]) == 0
	+	assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187
	+	assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187
	+	assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51
	+	assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51

← Older revision		Revision as of 02:50, 17 July 2020
Line 1:		Line 1:
−	~~==== 1 ====~~

−	~~Sum every range and keep track of the maximum.~~
−
−	~~Given a set of numbers N = { x0, x1 ... xn }~~
−
−	~~M = 0~~
−
−	~~for i in (0 .. n)~~
−	~~S[i, i] = xi~~
−	~~for j in (i + 1 .. n)~~
−	~~S[i, j] = S[i, j - 1] + xj~~
−	~~if M < S[i, j]~~
−	~~M = S[i, j]~~
−
−	~~==== 2 ====~~
−
−	~~def max_range(items):~~
−	~~max_diff = max(items[0], 0)~~
−	~~temp_diff = 0~~
−	~~for number in items:~~
−	~~temp_diff = max(0, temp_diff + number)~~
−	~~max_diff = max(max_diff, temp_diff)~~
−	~~return max_diff~~
−
−	~~assert max_range([1, 2, 3, 4, 5]) == 15~~
−	~~assert max_range([-1, -2, -3, -4, -5]) == 0~~
−	~~assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187~~
−	~~assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187~~
−	~~assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51~~
−	~~assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51~~

@@ Line 14: / Line 14: @@
         M = S[i, j]
-def max_range(items):
+==== 2 ====
-assert max_range([1, 2, 3, 4, 5]) == 15
+    assert max_range([1, 2, 3, 4, 5]) == 15
-assert max_range([-1, -2, -3, -4, -5]) == 0
+    assert max_range([-1, -2, -3, -4, -5]) == 0
-assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187
+    assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187
-assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187
+    assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187
-assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51
+    assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51
-assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51
+    assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51

@@ Line 40: / Line 40: @@
   my $max = max_range 31, -41, 59, 26, -53, 58, 97, -93, -23, 84;
-−
   print $max, "\n";