HackerRank #38 | SubArray | 🇧🇷

#java #subarray #array #wecoded

Este exercício me custou algumas muitas horas de resolução. Não tanto pelo enunciado, mas sim pelo desenvolvimento.
O problema pede para que peguemos um int n que vai delimitar a quantidade de elementos de um array. No exemplo, ele usa n = 5 e devolve um array com 5 elementos, separados por espaço.

5
1 -2 4 -5 1

O intuito é de fazer subarrays a partir desse array, sendo que cada subarray pode ter 1 ou mais posições. Exemplos de arrays que podem ser formados:

Subarrays que podem ser formados começando na posição 0:

[1]
[1, -2]
[1, -2, 4]
[1, -2, 4, -5]
[1, -2, 4, -5, 1]

Subarrays que podem ser formados começando na posição 2:

[4]
[4, -5]
[4, -5, 1]

Subarrays que podem ser formados começando na posição 4:
[1]

Agora que já sabemos como são feitos os subarrays, queremos saber quanto será o resultado da soma deles. Por exemplo:

[1] = 1
[1, -2] = -1
[1, -2, 4] = 3
[1, -2, 4, -5] = -2
[1, -2, 4, -5, 1] = -1

O problema pede para descobrirmos quantos subarrays têm como resultado somas negativas. No caso acima, 3 subarrays têm resultados negativos, mas sabemos que ainda podemos fazer vários outros subarrays e para isso precisamos contabilizar a soma array por array.

=======

Para resolver esse problema, segui o passo a passo:

Escaneei o int n
Fiz um novo array com n elementos: int[] array = new int[n]
Fiz um for que escaneia os valores para todos os n elementos

        Scanner scanner = new Scanner(new File("input.txt"));
        int n = scanner.nextInt();
        int[] array = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

Declarei a variável int sum = 0;
Declarei a variável int negativeSum = 0;
Fiz dois for, um dentro do outro. O primeiro for (j) serve para fixar a primeira posição do array, enquanto que o segundo for (z) vai percorrer todos os elementos seguintes.

        for (int j = 0; j < array.length; j++) {
            for (int z = j; z < array.length; z++) {
              Boolean isNegativeSum = negativeSum(j,z, array);

Dentro do segundo for, será necessário passar um método booleano que faz a soma dos elementos dentro do array e confere se são negativos ou positivos (lembrando que queremos contar apenas os arrays que têm resultados negativos!)

O método passa j, z e array e faz mais uma iteração. Fica assim:

public static Boolean negativeSum(int j, int z, int[] array) {

        int sum = 0;
        for (int i = j; i <= z; i++) {
            sum += array[i];
        }

        if (sum < 0)
            return true;

        return false;

Por fim, ao retornar para a main depois de ter passado pelo método booleano, somamos, através da soma isNegativeSum++. Código final fica assim:

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        int sum = 0;
        int negativeSum = 0;
        for (int j = 0; j < array.length; j++) {
            for (int z = j; z < array.length; z++) {
                Boolean isNegativeSum = negativeSum(j,z, array);

                if (isNegativeSum) {
                    negativeSum++;
                }
            }
        }
        System.out.println(negativeSum);
    }

    public static Boolean negativeSum(int j, int z, int[] array) {

        int sum = 0;
        for (int i = j; i <= z; i++) {
            sum += array[i];
        }

        if (sum < 0)
            return true;

        return false;

    }

=======