Bricks Game

                            Solution in C :

In C++ :




#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stdio.h>
#include<map>
#include<ext/hash_map>
#include<ext/hash_set>
#include<set>
#include<string>
#include<assert.h>
#include<vector>
#include<time.h>
#include<queue>
#include<deque>
#include<sstream>
#include<stack>
#include<sstream>
#define MA(a,b) ((a)>(b)?(a):(b))
#define MI(a,b) ((a)<(b)?(a):(b))
#define AB(a) (-(a)<(a)?(a):-(a))
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ep 0.0000000001
#define Pi 3.1415926535897932384626433832795
using namespace std;
using namespace __gnu_cxx;
const long long  MO=1000000000+7;
int i,j,n,m,k;
int a[1000000];
long long s[1000000],su[1000000];
bool f[1000000];
long long sol(int x)
{
    if (x==n+1) return 0;
    if (f[x]) return s[x];
    if (n-x<=2) return s[x]=su[x];
    f[x]=1;
    s[x]=0;
    if (x+1<=n+1)s[x]=max(s[x],su[x]-sol(x+1));
    if (x+2<=n+1)s[x]=max(s[x],su[x]-sol(x+2));
    if (x+3<=n+1)s[x]=max(s[x],su[x]-sol(x+3));
}
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (i=n;i>=1;i--)
            su[i]=su[i+1]+a[i];
        for (i=1;i<=n;i++)
            f[i]=0;
        cout<<sol(1)<<endl;
    }
    return 0;
}








In Java :





import java.util.Scanner;

public class Solution {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        while (t-- > 0) {
            int n = scanner.nextInt();
            int a[] = new int[n];
            long[] b = new long[n];
            long c[] = new long[n + 1];

            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
                b[i] = -1;
            }

            c[n - 1] = a[n - 1];
            c[n] = 0;
            for (int i = n - 2; i >= 0; i--)
                c[i] = c[i + 1] + a[i];

            System.out.println(play(a, b, c, 0));
        }
    }

    private static long play(int[] a, long[] b, long[] c, int i) {
        int n = a.length;

        if (i == n)
            return 0;


        if (b[i] != -1)
            ;
        else if (i >= n - 3) {
            b[i] = 0;
            for (int j = i; j < n; j++)
                b[i] += a[j];
        } else {
            b[i] = a[i] + a[i + 1] + a[i + 2] + c[i + 3] - play(a, b, c, i + 3);
            b[i] = Math.max(a[i] + c[i + 1] - play(a, b, c, i + 1), b[i]);
            b[i] = Math.max(b[i], a[i] + a[i + 1] + c[i + 2] - play(a, b, c, i + 2));
        }

//        System.out.println("returning " + i + " : " + b[i]);
        return b[i];
    }

}








In C :





#include <stdio.h>
long long min(long long a, long long b) { return (a<b?a:b); }
int main() {
    int T,n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int t[n];
        long long best[n+3], suff[n+3];
        for (int i=n; i<n+3; i++) best[i] = suff[i] = 0;
        for (int i=0; i<n; i++) scanf("%d", &t[i]);
        for (int i=n-1; i>=0; i--) suff[i] = suff[i+1] + t[i];
        for (int i=n-1; i>=0; i--)
            best[i] = suff[i] - min(best[i+1], min(best[i+2], best[i+3]));
        printf("%lld\n", best[0]);
    }
    return 0;
}








In Python3 :





INF = 10**18

def one_test():
	n = int(input())
	a = list(reversed(list(map(int, input().split()))))
	dp = [0] * (n + 1)
	for i in range(n):
		take = 0
		dp[i + 1] = -INF
		for j in range(i, max(i - 3, -1), -1):
			take += a[j]
			dp[i + 1] = max(dp[i + 1], take - dp[j])
	# print("!!!", dp)
	return (sum(a) + dp[n]) // 2

t = int(input())
for i in range(t):
	print(one_test())