HackerRank Java Subarray
문제 링크 : https://www.hackerrank.com/challenges/java-negative-subarray/problem
We define the following:
- A subarray of an -element array is an array composed from a contiguous block of the original array's elements. For example, if , then the subarrays are , , , , , and . Something like would notbe a subarray as it's not a contiguous subsection of the original array.
- The sum of an array is the total sum of its elements.
- An array's sum is negative if the total sum of its elements is negative.
- An array's sum is positive if the total sum of its elements is positive.
Given an array of integers, find and print its number of negative subarrays on a new line.
Input Format
The first line contains a single integer, , denoting the length of array .
The second line contains space-separated integers describing each respective element, , in array .
The second line contains space-separated integers describing each respective element, , in array .
Constraints
Output Format
Print the number of subarrays of having negative sums.
sample input
5
1 -2 4 -5 1
sample output
9
Explanation
There are nine negative subarrays of :
Thus, we print on a new line.
간단하게, 연결되는 모든 subarray의 합을 검사하고 합이 음수인 경우 카운트해준다.
[1] = 1
[1,-2] = -1
[1,-2,4] = 3
[1,-2,4,-5] = -2
[1,-2,4,-5,1] = -1
[-2] = -2
[-2,4] = 2
[-2,4,-5] = -3
[-2,4,-5,1] = -2
[4] = 4
[4, -5] = -1
[4, -5, 1] = 0
[-5] = -5
[-5, 1] = -4
이런 식으로 모두 검사한다.
import java.util.*;
public class Solution {
private static int subArrCnt = 0;
private static ArrayList<Integer> subArr = new ArrayList<>();
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scn = new Scanner(System.in);
int elementsCount = scn.nextInt();
int[] arr = new int[elementsCount];
for (int i = 0; i < elementsCount; i++) {
arr[i] = scn.nextInt();
}
scn.close();
for ( int a = 0; a < arr.length; a++ ) {
for (int i = 0; i < arr.length; i++) {
for (int j = a; j <= i; j++) {
subArr.add(arr[j]);
}
int sum = 0;
if (subArr.size() > 0) {
for (int t : subArr) {
sum += t;
}
if ( sum < 0 )
subArrCnt++;
}
subArr.clear();
}
}
}
}
댓글
댓글 쓰기