Given an array of integers, find and print its number of negative subarrays on a new line

Question

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line.

My code is taking \$\mathcal{O}(n^2)\$ time. How can I improve this?

import java.util.Scanner;
public class Solution {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int numberOfInts = sc.nextInt();
 int[] arr = new int[numberOfInts];
 for (int i = 0; i < numberOfInts; i++) {
 arr[i] = sc.nextInt();
 }
 int count = 0;
 for (int i = 0; i < numberOfInts - 2; i++) {
 int sum = arr[i];
 if (arr[i] < 0) {
 count++;
 }
 for (int j = i + 1; j < numberOfInts; j++) {
 sum = sum + arr[j];
 if (sum < 0) {
 count++;
 }
 }
 }
 if (arr[numberOfInts - 1] < 0) {
 count++;
 }
 System.out.println(count);
 }
}

Answer 1

Your code doesn't work for an empty array. Therefore it is conceptually wrong.

You should rewrite your code to be easily and automatically testable. This means to extract the interesting part of the program and separate it from the rest. In this case, the interesting part is the given an array, find. The code should therefore look like this:

static int countNegativeSubarrays(int... numbers) {
 int count = 0;
 // Your code here
 return count;
}

This method can be called easily from a test method:

static void runSelfTest() {
 if (countNegativeSubarrays() != 0)
 throw new AssertionError();
 if (countNegativeSubarrays(-1) != 1)
 throw new AssertionError();
 if (countNegativeSubarrays(-1, -1) != 3)
 throw new AssertionError();
 if (countNegativeSubarrays(-1, -1, -1) != 6)
 throw new AssertionError();
 if (countNegativeSubarrays(1, -1, -2, 5) != 4)
 throw new AssertionError();
 // Add more test cases here
}

In your main method you should run this self-test before accepting any input from the user.