Difference between revisions of "TADM2E 8.21"

From Algorithm Wiki
Jump to: navigation, search
(→‎2)
(Removes an incorrect solution and presents what I believe is a correct O(n) solution to the max-range problem, with test cases.)
Line 14: Line 14:
 
       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
  
−
Sum from each end, resetting the prefix or suffix (i.e., discarding the summed numbers) if it goes negative.
 
  
−
#!/usr/bin/perl
+
assert max_range([1, 2, 3, 4, 5]) == 15
−
+
assert max_range([-1, -2, -3, -4, -5]) == 0
−
sub max_range
+
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
−
  my @numbers = @_;
+
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
−
  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";
 

Revision as of 18:26, 20 October 2017

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]

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

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_8.21&oldid=536"