DCEPC501

SPOJ-DCEPC501.cpp

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define MAX 100012
namespace IO{
  const int SIZE = 1 << 19;
	char buff[SIZE], *p = buff + SIZE;
	char read_char(){
		if( p == buff + SIZE ){
		    fread( buff, 1, SIZE, stdin );
		    p = buff;
		}
		return *(p++);
	}

	inline int read_int(){
		char c;
		while( !isdigit( c = read_char() ) );
		int r = c-'0';
		while( isdigit( c = read_char() ) ) r = 10*r + c - '0';
		return r;
	}
}
using namespace IO;
unsigned long long res[MAX];
unsigned l1,l2,l3, in[MAX];
#define MAXX(a,b) (a)>(b)?(a):(b)
int main(){
	int TC, N;
	cin >> TC;
	while(TC--){
		//cin >> N;
		N=read_int();
		for(int i=N-1;i>=0;i--)
			//cin >> in[i+10]; // index starts from 10.............reversed
			in[i+10]=read_int();
		l1=l2=l3=0;
		for(int c=0,i=10;c<N;i++,c++)
		{
			l1=l1+in[i]-in[i-1];
			l2=l2+in[i]-in[i-2];
			l3=l3+in[i]-in[i-3];
			res[i]=res[i-2]+l1;
			res[i]=MAXX(res[i], res[i-4]+l2);
			res[i]=MAXX(res[i], res[i-6]+l3);
			//cout << res[i] << ' ' << l1 << ' ' << l2 << ' '<< l3 << endl;
		}
		cout << res[N+10-1] << endl;
	}
	return 0;
}