• + 2 comments

    First approach: Time Complexity: O(n^3)

    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            int n = sc.nextInt();
            
            int[] array = new int[n];
            
            for(int i = 0; i < n; i++) {
                array[i] = sc.nextInt();
            }
            
            System.out.println(countSubarraysWithNegativeSums(array));
            
            sc.close();
        }
        
        private static int countSubarraysWithNegativeSums(int[] array) {
            int count = 0;
            int currentSum;
            
            // Look all the possible subArrays and check it sums
            for(int i = 1; i <= array.length; i++) {
                for(int j = 0; j <= array.length - i; j++) {
                    currentSum = 0;
                    for(int z = 0; z < i; z++) {
                        currentSum += array[j + z];
                    }
                    
                    if(currentSum < 0)
                        count++;
                }
            } 
        
        return count;
    }
    				
    				
    //Second Approach: Time Complexity O(n^2)
    
    private static int countSubarraysWithNegativeSums(int[] array) {
        int count = 0;
        int currentSum;
        int n = array.length;
        
        // Look all the possible subArrays and check 
        for (int start = 0; start < n; start++) {
            currentSum = 0;
            for (int end = start; end < n; end++) {
                currentSum += array[end];
                
                if (currentSum < 0)
                    count++;
                
            }
        }
    		
            return count;
        }