Find the longest sub-array in which the sum of elements is equal to a given number.

longest_sub_array_sum_k.py

# Shape a matrix and we only use the half
# in which the col-number >= row-number!
# m[i][j] stores the sum of values in the
# sub-array from i to j (i.e nums[i:(j + 1)])
# and to calculate each new sub-array we can
# leverage the previously calculated sub-array
# which didn't have this new element and add
# this new element on top of that:
#
#   m[i][j] = m[i][j - 1] + nums[j]
#
# Check out the sample matrix for the given
# input at the bottom!

# Time : O(n^2)
# Space: O(n^2)
def longest_sub_arr_sum_k(nums, k):
  n            = len(nums)
  m            = [[0] * n for i in xrange(0, n)]
  mx_sub_range = (-1, -1)
  mx_sub_len   = -1

  for i in xrange(0, n):
    m[i][i] = nums[i]

  for l in xrange(2, n + 1):
    for i in xrange(0, n - l + 1):
      j       = i + l - 1
      m[i][j] = m[i][j - 1] + nums[j]
      if m[i][j] == k and (j - i + 1) > mx_sub_len:
        mx_sub_len   = j - i + 1
        mx_sub_range = (i, j)

  beg, end = mx_sub_range
  return (mx_sub_len, nums[beg:(end + 1)])

nums        = [3, 2, 5, 1, 1, 2, -1, 2]
length, sub = longest_sub_arr_sum_k(nums, 5)
print(length) #=> 5
print(sub)    #=> [1, 1, 2, -1, 2]

#     0   1    2    3    4    5    6    7
# 0 | 3 | 5 | 10 | 11 | 12 | 14 | 13 | 15
#----------------------
# 1 |   | 2 |  7 |  8 |  9 | 11 | 10 | 12
#----------------------
# 2 |   |   |  5 |  6 |  7 |  9 |  8 | 10
#----------------------
# 3 |   |   |    |  1 |  2 |  4 |  3 |  5
#----------------------
# 4 |   |   |    |    |  1 |  3 |  2 | 4
#----------------------
# 5 |   |   |    |    |    |  2 |  1 | 3
#----------------------
# 6 |   |   |    |    |    |    | -1 | 1
#----------------------
# 7 |   |   |    |    |    |    |    | 2