문제
n크기의 배열에서, a ~ b까지의 인덱스에 k 만큼 더한 후 가장 큰 값을 리턴하는 문제
ex)
입력 : int n = 10, int [] queries
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
3 | 3 | 3 | 3 | 3 | |||||
7 | 7 | 7 | 7 | 7 | |||||
1 | 1 | 1 | 1 |
합계가 가장 큰 값은 인덱스 4,5에 해당하는 10이 됨
arr[1] = 3
arr[2] = 3
arr[3] = 3
arr[4] = 3 + 7=10
arr[5] = 3 + 7=10
arr[6] = 7 + 1 = 8
arr[7] = 7 + 1 = 8
arr[8] = 7 + 1 = 8
arr[9] = 1
arr[10] = 0
풀이방법
a인덱스에 k값을 넣고 b+1 인덱스에 -k값을 넣음
n크기인 배열의 누적합 중 가장 큰 값을 리턴
최댓값만 구하는 것이기 때문에 값이 언제 들어가는지만 유의하면 된다.
예를들어 1 ~ 4인덱스까지만 3을 추가한다면 1 ~ 5 인덱스의 각 합은 3, 3, 3, 3, 0이다.
누적합으로 구하게 되면 인덱스 1에서 +3 , 인덱스 2 ~ 4 는 +0으로 누적합 유지,
인덱스 5에서는 -3을 하여 누적합을 0으로 만들 수 있다.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
3 | -3 | ||||||||
7 | -7 | ||||||||
1 | -1 |
인덱스 누적합
arr[1] = 3
arr[2] = 3 + 0
arr[3] = 3 + 0
arr[4] = 3 + 7=10
arr[5] = 10 + 0
arr[6] = 10 - 3 + 1 = 8
arr[7] = 8 + 0
arr[8] = 8 + 0
arr[9] = 8 - 7
arr[10] = 1 - 1
답
'알고리즘 > C#' 카테고리의 다른 글
Hash Tables: Ransom Note c# (0) | 2020.04.15 |
---|---|
New Year Chaos c# (1) | 2020.04.05 |
Arrays: Left Rotation C# (0) | 2020.03.27 |
Jumping on the Clouds C# (0) | 2020.03.21 |
Repeated String C# (0) | 2020.03.21 |
WRITTEN BY