Array Manipulation c#

문제 

 

n크기의 배열에서, a ~ b까지의 인덱스에 k 만큼 더한 후 가장 큰 값을 리턴하는 문제

 

ex)

입력 : int n = 10, int [] queries

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

 

 

답