如何打印给定数组中负子数组的数量？

Question

问题陈述：

给定一个包含 n 个整数的数组，找出它的负子数组的个数并在新行上打印出来。（如果其元素的总和为负，则子数组为负。）

样本输入

5

1 -2 4 -5 1

示例输出

9

我的代码产生的结果

Input (stdin)

5

1 -2 4 -5 1

Your Output (stdout)

7

Expected Output

9

Compiler Message

Wrong Answer

我的代码：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a[] = new int[n];
        int b[] = new int[n];
        int count=0;
        int i,j,sum = 0;
        for(i=0;i<n;i++)
            {
            a[i] = scan.nextInt();            
        }
        for(i=0;i<n;i++)
            {
        if(a[i]<0){count++;}
        }
        for(i=0;i<n;i++)
            {
            for(j=0;j<n;j++)
                {
            sum = a[i] + sum;
            b[j] = sum;
            }
        }
        for(j=0;j<n;j++)
                {
        if(b[j]<0){count++;}
        }
        System.out.println(count);
        
    } 
}

我哪里错了？

Answer 1

对之前的逻辑做了一些改动，现在这段代码可以正常工作了。

import java.util.*;
public class Solution {

      public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int a[] = new int[n];
            int count=0;
            int i,j,sum = 0;
            for(i=0;i<n;i++)
            {
                a[i] = scan.nextInt();
            }
            scan.close();
            for(i=0;i<n;i++)
            {
                sum = 0;
                for(j=i;j<n;j++)
                {
                    sum = a[j] + sum;
                    if(sum<0){
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

Answer 2

O(nlogn) 中的解决方案运行，基于计数反转的想法

计算给定输入的前缀和数组，它包含累加和
在prefix[i] > prefix[j] when i < j时计算前缀和数组的反转，在prefix[j] < 0

时间复杂度像merge-sort一样分析

import java.util.*;

public class NegativeSumSubarray {

    public static void main(String[] args) {
        int[] array = { 1, -2, 4, -5, 1 };

        int[] prefixSum = new int[array.length];
        prefixSum[0] = array[0];
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + array[i];
        }

        int count = countInversion(prefixSum, 0, prefixSum.length - 1);
        System.out.println(count); // 9
    }

    public static int countInversion(int[] prefixSum, int left, int right) {
        // merge-sort like counting inversion in prefixSum array
        if (left == right) {
            if (prefixSum[left] < 0) {
                return 1;
            }
            return 0;
        }
        int mid = (left + right) / 2;
        int count_left = countInversion(prefixSum, left, mid);
        int count_right = countInversion(prefixSum, mid + 1, right);
        int count_cross = countCrossInversion(prefixSum, left, mid, right);
        return count_left + count_right + count_cross;
    }

    public static int countCrossInversion(int[] prefixSum, int left, int mid, int right) {
        List<Integer> L = new ArrayList<>();
        for (int i = left; i <= mid; i++) {
            L.add(prefixSum[i]);
        }
        L.add(Integer.MAX_VALUE);

        List<Integer> R = new ArrayList<>();
        for (int i = mid + 1; i <= right; i++) {
            R.add(prefixSum[i]);
        }
        R.add(Integer.MAX_VALUE);

        int count = 0;
        int i = 0;
        int j = 0;
        for (int k = left; k <= right; k++) {
            if (L.get(i) <=  R.get(j)) {
                prefixSum[k] = L.get(i);
                i += 1;
            } else {
                prefixSum[k] = R.get(j);
                count += L.size() - 1 - i; // size() counts additional sentinal MAX_VALUE
                j += 1;
            }
        }
        return count;
    }
}

如何打印给定数组中负子数组的数量？

How do I print the number of negative subarrays from a given array?

java

sub-array