base case: m[0] = input[0]
induction rule: m[i] represents [within the range from the beginning to the i-th element] the largest sum of the subarray(including the i-th element)
m[i] = m[i - 1] + input[i] if m[i - 1] >= 0
input[i] otherwise
time: O(n)
space: O(n) -> can optimize to O(1) because we only need to record the sum before.