This content originally appeared on DEV Community and was authored by Beatriz Maciel
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
nelementos:int[] array = new int[n] - Fiz um for que escaneia os valores para todos os
nelementos
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 primeirofor (j)serve para fixar a primeira posição do array, enquanto que o segundofor(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
This content originally appeared on DEV Community and was authored by Beatriz Maciel
Beatriz Maciel | Sciencx (2021-09-14T21:03:14+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/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.