Finding the count of negative sub-arrays for a given array

I want to improve my implementation for the following problem:


You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that sub-array is negative. Count the number of "Negative sub-arrays" in the input array.


Note: Subarrays are contiguous chunks of the main array. For example if the array is {1,2,3,5} then some of the subarrays are {1}, {1,2,3}, {2,3,5}, {1,2,3,5} etc. But {1,2,5} is not an subarray as it is not contiguous.

Input Format:


The first line consists an integer n. The next line will contain n space seperated integers. Value of n will be at most \$100\$. The numbers in the array will range between \$-10000\$ to \$10000\$.

Output Format:


Print the answer to the problem.

I am using two loops. It's clearing the test cases, but can I do it with only one loop?

import java.io.*;
import java.util.*;

   public class Solution {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte T = Byte.parseByte(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[T];
        for(int i = 0; i < T; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int sum = 0, count = 0;;
        for(int i = 0; i < T; i++){
             sum = 0;
             sum += arr[i];// If the number itself is negative count++
              if(sum < 0){
                    count++;
                }
            for(int j = i + 1; j < T; j++){
                sum += arr[j];
                if(sum < 0){// If the most recent sum is -ve, count++
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

Simplifications

If you look at your main loop:

int sum = 0, count = 0;;
    for(int i = 0; i < T; i++){
         sum = 0;
         sum += arr[i];// If the number itself is negative count++
          if(sum < 0){
                count++;
            }
        for(int j = i + 1; j < T; j++){
            sum += arr[j];
            if(sum < 0){// If the most recent sum is -ve, count++
                count++;
            }
        }
    }

you can see that there are two blocks of code that do the same thing. You can remove one block by noticing that starting the j loop at i instead of i+1 will do the initial check of the number itself. Another thing you could do is move the int sum declaration inside the for loop. So the final result would look like this:

int count = 0;
    for (int i = 0; i < T; i++) {
        int sum = 0;
        for (int j = i; j < T; j++) {
            sum += arr[j];
            if (sum < 0) {// If the most recent sum is -ve, count++
                count++;
            }
        }
    }

Complexity

As far as your complexity question, I don't believe that you can solve this problem with better than an \$O(n^2)\$ solution, so your two loops seem fine.

StackExchange Code Review Q#100446, answer score: 3