max_sum_subarray.rb

#Problem- find the subarray having maximum sum


class SubArray
  attr_reader :start, :end
  attr_accessor :sum

    def initialize n
      @start = 0
      @end = 0
      @sum = -9 * n #max negative sum for 'n' length array
    end

    def set_start_end(array_start, array_end)
      @start, @end = array_start, array_end
    end
  end


  class MaxSubArray
    def find(array)
      length = array.size
      max = SubArray.new(length)
      cur = SubArray.new(length)

      for i in 0...length
        cur.sum = cur.sum + array[i]
        if (cur.sum > max.sum)
          max.sum = cur.sum
          cur.set_start_end(cur.start, i)
          max.set_start_end(cur.start, i)
        elsif (cur.sum < 0)
          if array[i+1] != nil && (array[i] > array[i+1])
            cur.set_start_end(i, i)
          else
            cur.sum = 0
            cur.set_start_end(i + 1, i + 1)
          end
        end
      end
      array.slice(max.start, max.end - max.start + 1)
    end
  end


  puts MaxSubArray.new.find [1,2,3,4]     #=> [1,2,3,4]
  puts MaxSubArray.new.find [1,-2,3,4]    #=> [3,4]
  puts MaxSubArray.new.find [-1,-2,-3,0]  #=> [0]
  puts MaxSubArray.new.find [-1,-2,-3,-4] #=> [-1]