HackerRank #38 | SubArray | ??

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 …

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;

    }

=======



Referências:

How to create a subarray from another array : StackOverFlow

Java array sum average : Baeldung


Print Share Comment Cite Upload Translate
APA
Beatriz Maciel | Sciencx (2024-03-28T22:26:50+00:00) » HackerRank #38 | SubArray | ??. Retrieved from https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/.
MLA
" » HackerRank #38 | SubArray | ??." Beatriz Maciel | Sciencx - Tuesday September 14, 2021, https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/
HARVARD
Beatriz Maciel | Sciencx Tuesday September 14, 2021 » HackerRank #38 | SubArray | ??., viewed 2024-03-28T22:26:50+00:00,<https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/>
VANCOUVER
Beatriz Maciel | Sciencx - » HackerRank #38 | SubArray | ??. [Internet]. [Accessed 2024-03-28T22:26:50+00:00]. Available from: https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/
CHICAGO
" » HackerRank #38 | SubArray | ??." Beatriz Maciel | Sciencx - Accessed 2024-03-28T22:26:50+00:00. https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/
IEEE
" » HackerRank #38 | SubArray | ??." Beatriz Maciel | Sciencx [Online]. Available: https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/. [Accessed: 2024-03-28T22:26:50+00:00]
rf:citation
» HackerRank #38 | SubArray | ?? | Beatriz Maciel | Sciencx | https://www.scien.cx/2021/09/14/hackerrank-38-subarray-%f0%9f%87%a7%f0%9f%87%b7/ | 2024-03-28T22:26:50+00:00
https://github.com/addpipe/simple-recorderjs-demo