# Counting contiguous subarrays with a negative sum

I'm doing a coding challenge that asks to count the number of contiguous subarrays that have a negative sum:

A subarray of an n-element array is an array composed from a contiguous block of the original array'selements. For example, if array = [1,2,3], then the subarrays are [1], [2], [3], [1,2], [2,3], and [1,2,3]. Something like [1,3] would not be a subarray as it's not a contiguous subsection of the original array.

The sum of an array is the total sum of its elements. An array's sum is negative if the total sum of its elements is negative. An array's sum is positive if the total sum of its elements is positive. Given an array of integers, find and print its number of negative subarrays on a new line.

I wrote this method and I'm trying to figure out the runtime for it but I'm not sure how to handle the loop and the recursion. Assume the length of array a is > 0.

int numNegatives(int[] a){

if(a.length == 1){
if(a[0] < 0){ return 1; } else { return 0; }
}

int count = 0;
int sum = 0;

for(int i = 0; i < a.length; i++){ //N
sum += a[i];
if(sum < 0){ count++; }
}
count += numNegatives(Arrays.copyOfRange(a, 1, a.length));//N-1

return count;
}


The for loop will be O(N), since it loops over the array, and I believe the recursion call will then be O(N-1). Since the recursion call is outside the for loop, does that make the total O(N)? Most solutions to this challenge are two nested for loops with O(N²) runtime, and so I'm not sure if I actually made any improvement. Is it worse than O(N²)?

• Can you include more of the requirements of the coding challenge? Also, if it is publicly available on the Internet then a link can be included but ensure the main parts are contained in the description of your post – Sᴀᴍ Onᴇᴌᴀ Jul 16 '18 at 23:24
• @SamOnela made the requested edits. Definitely was missing important information, so thank you. Let me know if there is anything else. – Richard Jul 16 '18 at 23:31

• Recurse for every element in the list, so the depth of the recursion tree is of the order n.
• For each layer, there is the for loop, which is of the order n, and the array copying, which is also of the order n. So for each layer, there of the order O(n) amount of work to do.
So the algorithm does have complexity O(n^2). Also, is it really necessary to make the copy of the array each time? If your function had a second int start parameter (which is incremented with each recursive call), you could begin the for loop from further down the array with each recursive call, without the need for copies.