From: Aureliano Calvo <aurelianocalvo@...>
Date: 2007-07-15T21:30:59+09:00
Subject: [QUIZ-Solution] Maximum Sub-Array (#131)

Given that the spoiler time is finished (I think) these are my
solutions to the Quiz #131. I only worked on single arrays (and not
matrixes). If found 3 different solutions. The first one just searches
through the solution space and calculates the value for each subarray.
It takes O(n^3). The second one uses that the sum is associative to
use the previous calculation for the sum of a subarray to decrese the
time complexity to O(n^2). And, in the end, I've found a way to find
the max sub array in a single pass O(n). All the solutions have
constant space constraints (O(1)).

Here is the code (also at http://pastie.caboo.se/78970):
#!/usr/bin/env ruby

class Array

  # Runs in O(n^3), change the value function and find using any
objective function.
  def max_subarray_original

    better_subarray = []
    better_value = 0
    (0...self.length).each do |start|
      (start...self.length).each do |finish|
        value = value(start, finish)
        if (value > better_value) then
          better_value = value
          better_subarray = self[start..finish]
        end
      end
    end

    better_subarray
  end

  def value(start, finish)
    self[start..finish].inject(0) { |acum, value| acum+value }
  end

  # Runs in O(n^2), uses the sum asociativity to avoid an iteration
through the array.
  def max_subarray_optimized

    better_subarray = []
    better_value = 0
    (0...self.length).each do |start|
      value = 0
      (start...self.length).each do |finish|
        value += self[finish]
        if (value > better_value) then
          better_value = value
          better_subarray = self[start..finish]
        end
      end
    end

    better_subarray
  end

  # It's technically imposible to improve it in time or space complexity.
  # Runs in O(n) time and O(1) space*.
  # * Assumes that each number takes the same space in memory and that
additions, substractions and comparisions take constant time.
  def max_subarray_single_pass

    sum = 0
    min_pos = -1
    min_value = 0
    min_pos_at_left = -1
    min_value_at_left = 0
    better_end_pos = -1
    better_value = 0

    self.each_with_index do
      |value, index|
      sum += value
      if sum - min_value > better_value then
        better_value = sum - min_value
        better_end_pos = index
        min_value_at_left = min_value
        min_pos_at_left = min_pos
      end
      if sum < min_value then
        min_value = sum
        min_pos = index
      end
    end

    return [] if better_end_pos == -1
    return self[(min_pos+1)..better_end_pos]
  end
end

# some manual testing
[[-1, 2, 5, -1, 3, -2, 1],
[1, -1000, 100],
[-3, -2, -1]].each do
|array|

  puts "array"
  p array

  puts "max_subarray_original"
  p array.max_subarray_original

  puts "max_subarray_optimized"
  p array.max_subarray_optimized

  puts "max_subarray_single_pass"
  p array.max_subarray_single_pass
end