Lv.4arraymonotonic-stackprefix-sumstack
최솟값과 구간 합의 곱
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
양의 정수로 이루어진 배열 A가 주어집니다.
비어 있지 않은 연속 부분배열을 하나 고를 때, 그 구간의 최솟값 × 구간 합이 최대가 되는 값을 반환하세요.
입출력 예
| A | result |
|---|---|
[1, 2, 3, 2] | 14 |
[5] | 25 |
[3, 1, 6, 4, 5] | 60 |
입출력 예 설명
예 1 — [2, 3, 2]를 고르면 최솟값 2, 합 7이라 14입니다. 전체 [1,2,3,2]는 최솟값 1, 합 8로 8밖에 안 됩니다.
예 2 — 원소 하나뿐이라 최솟값 5, 합 5로 25입니다.
예 3 — [6, 4, 5]를 고르면 최솟값 4, 합 15라 60입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(A: int[]) → long
Constraints
- 답은 64비트 정수 범위입니다.
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| A | Expected |
|---|---|
[1,2,3,2] | 14 |
[5] | 25 |
[3,1,6,4,5] | 60 |
Hint
Hint
각 원소를 "이 원소가 최솟값이 되는 구간"의 대표로 생각하세요.
A[i]가 최솟값인 가장 넓은 구간은, 왼쪽으로 A[i]보다 작은 값을 만날 때까지, 오른쪽으로도 마찬가지로 뻗은 범위입니다. 그 구간보다 좁히면 합만 줄어들어 손해이므로, 각 i마다 이 최대 구간만 보면 충분합니다.
그러면 두 가지가 필요합니다.
left[i]—i왼쪽에서A[i]보다 작은 첫 인덱스 (없으면-1)right[i]—i오른쪽에서A[i]보다 작은 첫 인덱스 (없으면N)
이건 단조 스택 한 번으로 둘 다 구할 수 있습니다. while로 자기보다 큰 것들을 꺼내 right를 채우고, 꺼낸 뒤 스택 맨 위가 바로 left입니다.
구간 합은 누적합으로 에 꺼내세요.
복잡도 목표
모든 구간을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 5 | verdict only |