코드업 4424 / 백준 2670 : 연속 부분 최대곱

https://codeup.kr/problem.php?id=4424 

연속 부분 최대곱

https://www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

연속부분 최대합이 포인트다.

쭉 연속해서 곱하는게 원칙

곱하다가 지금 만나는 값이랑 비교해서 여태까지 만든 맥스보다크면

그걸 버리고 새로만난 아이부터 값을 곱해나가면 된다.

#include <stdio.h>

int main() {
	double arr[10000] = {0,};
	double dp_arr[10000];

	int N;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%lf", &arr[i]);
	}

	// set initial value
	dp_arr[0] = arr[0];
	double max = dp_arr[0];

	// processing
	for (int i = 1; i <= N; i++) {
		// continue mul until now max < now value
		if (dp_arr[i - 1] > 1) {
			dp_arr[i] = arr[i] * dp_arr[i-1];
		}
		else {
			// dp_arr[i-1] < 1, do not multiply
			dp_arr[i] = arr[i] * 1;
		}
		max = (max > dp_arr[i]) ? max : dp_arr[i];
	}

	printf("%.3f", max);

	return 0;
}

사실 지금까지 곱해온 값 (dp_arr[i]) 와

바로 이전까지 곱해온 값 (dp_arr[i-1]) 기억하면 되어서

 

각각 now, before 변수로 바꾸어 코드를 작성해봤다.

#include <stdio.h>

int main() {
	double arr[10000] = {0,};
	double now, before;

	int N;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%lf", &arr[i]);
	}

	// set initial value
	now = before = arr[0];
	double max = now;

	// processing
	for (int i = 1; i <= N; i++) {
		// continue mul until now max < now value
		if (before > 1) {
			now = arr[i] * before;
		}
		else {
			// dp_arr[i-1] < 1, do not multiply
			now = arr[i] * 1;
		}
		max = (max > now) ? max : now;
		before = now;
	}

	printf("%.3f", max);

	return 0;
}