This is known as the http://en.wikipedia.org/wiki/Maximum_subarray_problem and is a typical interview question!
Most people --me included-- would solve it using a O(n^2) algorithm but there is in fact a much better algorithm with O(n) complexity. Here is an R implementation of Kadane's algorithm from the link above:
max_subarray <- function(A) {
max_ending_here <- 0
max_so_far <- 0
for (x in A) {
max_ending_here <- max(0, max_ending_here + x)
max_so_far <- max(max_so_far, max_ending_here)
}
max_so_far
}
Since in your case, you are looking for the minimum sub-array sum, you would have to call it like this:
-max_subarray(-diffP)
[1] -2
(Or you can also rewrite the function above and replace max
with min
everywhere.)
Note that, yes, the implementation still uses a for
loop, but the complexity of the algorithm being O(n) (meaning the number of operations is of the same order as length(diff)
), it should be rather quick. Also, it won't consume any memory since it only stores and updates a couple variables.