path: root / Year 2 / Design and analysis of algorithms / Practicum / Homeworks / HW4-Sequence.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

long long n;
long long mult2[100010] = { 0 }, mult3[100010] = { 0 };

int main() {
	scanf("%lld", &n);
	for (long long i = 0; i < n; i++) {
		long long t;
		scanf("%lld", &t);
		mult2[i] = t*2;
		mult3[i] = t*3;
	}

	for (long long i = 1; i < n; i++) {
		mult2[i] += max(mult2[i-1], mult3[i-1]);
		mult3[i] += mult2[i-1];
	}
	printf("%lld", max(mult2[n-1], mult3[n-1]));
}