Cod sursa(job #131198)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 3 februarie 2008 13:07:31
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#include <math.h>

long n, i, sum, a[100010], c[100010], maxim;

long max(long num1, long num2) {
	if (num1 < num2) {
		return num2;
	}
	return num1;
}

int main() {
	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &a[i]);
	}
	//dinamica I
	c[1] = a[1];
	for (i = 3; i < n; ++i) {
		sum = a[i] + a[i - 1];
		if (i > 3) {
			sum += c[i - 3];
		}
		c[i - 1] = max(sum, c[i - 1]);
	}
	maxim = c[n - 1];
	
	//dinamica II
	c[2] = a[2] + a[3];	
	for (i = 3; i <= n; ++i) {
		sum = a[i] + a[i - 1];
		if (i > 3) {
			sum += c[i - 3];
		}
		c[i - 1] = max(sum, c[i - 1]);
	}
	printf("%ld", max(maxim, c[n - 1]));
	
	return 0;
}