LeetCode Q053 Maximum Subarray

Q053 Maximum Subarray



Start from the simplest example [-2]
 [-2] the result can only be -2
 We've got f(0) = -2

 Next, 2 numbers
 [-2, 1]
 for 1, the better solution would be ignore -2
 f(1) = max(num(1), num(1) + f(0))

 Thus, f(n): if we choose number[n], what would be the maximum sum of the contiguous subbarray ending at number[m]
 f(n) = max(num[n], num[n] + f(n -1))

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q053MaximumSubarray.playground/Contents.swift