8012 : 최대 부분합 수열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열이 주어집니다. 연속된 부분배열들의 합 중 가장 큰 값을 $X$라고 할 때, 다음 두 가지 값을 구하는 프로그램을 작성하십시오.
1. 최대 부분배열 합 $X$
2. 합이 $X$가 되는 서로 다른 연속된 부분배열의 개수
[제약 조건]
• $1 \le T \le 20$ (테스트 케이스 수)
• $1 \le N \le 10^5$
• $-10^4 \le A_i \le 10^4$
1. 최대 부분배열 합 $X$
2. 합이 $X$가 되는 서로 다른 연속된 부분배열의 개수
[제약 조건]
• $1 \le T \le 20$ (테스트 케이스 수)
• $1 \le N \le 10^5$
• $-10^4 \le A_i \le 10^4$
입력 설명
첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스의 첫째 줄에는 배열의 크기 $N$이 주어집니다.
둘째 줄에는 $N$개의 정수가 공백으로 구분되어 주어집니다.
각 테스트 케이스의 첫째 줄에는 배열의 크기 $N$이 주어집니다.
둘째 줄에는 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
각 테스트 케이스마다 최대 부분배열 합과 그 합을 달성하는 부분배열의 개수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
4
3 -1 -1 -1
5
4 2 0 -2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3 1
6 2도움
1. 카데인 알고리즘으로 최대 부분배열 합 $X$를 먼저 구합니다.
2. 누적합(Prefix Sum)과 해시 맵(빈도수 테이블)을 사용하여 $prefix[R] - prefix[L-1] = X \iff prefix[L-1] = prefix[R] - X$를 만족하는 $(L, R)$ 쌍의 개수를 $O(N)$ 시간에 카운트합니다.
2. 누적합(Prefix Sum)과 해시 맵(빈도수 테이블)을 사용하여 $prefix[R] - prefix[L-1] = X \iff prefix[L-1] = prefix[R] - X$를 만족하는 $(L, R)$ 쌍의 개수를 $O(N)$ 시간에 카운트합니다.