[C++] 온도의 최대값 ( 시간 제한 )

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰값을 계산하는 프로그램을 작성하시오.

#include<stdio.h>
#include<vector>

int main() {
	int n, k, i;
	scanf("%d %d", &n, &k);
	std::vector <int> a(n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int max; int sum = 0;
	for (i = 0; i < k; i++) { sum += a[i]; }
	max = sum;

		// [i-k] 값을 빼고 [i]값을 더해서 k개 개수 유지
		// 이중 for문 없이 시간복잡도 n으로 해결할 수 있다.
	for (i = k; i < n; i++) {
		sum = sum + (a[i] - a[i-k] );
		max = (sum > max ? sum : max);
	}
	printf("%d", max);
}

k 일 동안의 온도의 합이 가장 큰 값을 찾아야한다. 

만약에 i = 0부터 i < n까지 for문을 돌고 또 다시 그 안에서 j = i; j <= i+k for문을 돈다면 시간 초과다.

 

-  0 ~ k 까지의 온도의 합을 max의 초기값으로 한다. 

- 그 다음엔 0을 빼고 k+1 값을 더하면 k 개수를 유지하되, for문을 또 돌릴 필요없이 k일동안의 온도의 합을 구할 수 있다.

- i = k 부터 i <n 까지 for문을 돌면서 최대값을 구한다.