max_subarray.rb

# **PROBLEM STATEMENT**
#Given a finite sequence of integers A,
# find the finite contiguous subsequence S s.t. the Σ(S) := "sum of the elements of S", is maximum.

# **OPTIMAL SUBSTRUCTURE**
# Claim: Consider the problem of obtaining the contig. subsequence w/ max sum
# up to and including the ith element of A. Suppose S = S(k) is the optimal solution
# of the sequence A, where k is the index in A of the last element in the solution.
# That is, among all candidate solutions, Σ(S) is maximum and A[k] is the last element in S.
# Let F = S[-1] be a focring factor. Then, S' = S[:-1] is the contig. subsequence
# w/ maximum sum to the subproblem with force F ( i.e. Σ(S(k-1)F) = Σ(S'F) ).

# Proof: For contradiction suppose that Σ(S(k-1)) > Σ(S'). Then Σ(S(k-1)F) > Σ(S),
# which contradicts the maximality of S. Thus, it has to be that Σ(S(k-1)F) = Σ(S'F) = Σ(S).

# **OVERLAPPING SUBPROBLEMS**
# Any S(i+p) for some fixed i>0 and p = {1,..,|A|-1-i} will recompute S(i).

# **RECURRENCE RELATION**
# S[i] = max{ S[i-1] + A[i], A[i] }

A = [-5, 4, 3, -1]
# S = S[2] = [4, 3] is maximum.
# Σ(S) = 7

def max_subarray_dp a
  n = a.length
  s = [ a[0] ] #holds max sum up to and including the ith element
  r = [0] #holds starting index of max subarray of the ith element
  for i in 1..n-1

    if s[i-1] + a[i] > a[i]
      s[i] = s[i-1] + a[i]
      r[i] = r[i-1]
    else
      s[i] = a[i]
      r[i] = i
    end

  end

  return s, r
end

sum, indices =  max_subarray_dp A
print sum
print indices
print "\n"

def max_subarray_brutef a
  n = a.length
  max_sum = start = finish = 0
  for i in 0..n-1
    sum = 0
    for j in i..n-1
      sum += a[j]
      if sum > max_sum
        max_sum = sum
        start = i
        finish = j
      end
    end

  end
  return [max_sum, start, finish]
end