HackerRank Bricks Game problem solution

In this HackerRank Bricks Game problem solution, You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2, or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Problem solution in Python.

def maxScore(n,seq):
    prefixSum = [seq[0],seq[0]+seq[1],seq[0]+seq[1]+seq[2]]
    table = [seq[0],seq[0]+seq[1],seq[0]+seq[1]+seq[2]]
    
    if n < 4: return table[-1]
    
    for i in range(3,n):
        prefixSum.append(prefixSum[-1]+seq[i])
        
        best = 0
        
        for x in (0,1,2):
            a = sum(seq[i-x:i+1])
            b = prefixSum[i-x-1]
            c = table[i-x-1]
            best = max(a+b-c,best)
            pass
        
        table.append(best)
        
        pass
    
    
    return table[-1]

if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        n = int(input())
        seq = list(map(int,input().split()))
        seq.reverse()
        print(maxScore(n,seq))
        pass

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    static int max;
    static int a[];
    static long b[];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t!=0){
            t--;
        int n=sc.nextInt();
        a=new int[n];
        b=new long[n];
            int c[]=new int[n];
            long dp[]=new long[n];
        max=0;
        long s=0;
            for(int i=0;i<n;i++){
                c[i]=sc.nextInt();
            }
        for(int i=0;i<n;i++){
            a[i]=c[n-1-i];
            s=s+a[i];
            b[i]=s;
            if(i<=2)
                dp[i]=b[i];
            else{
                dp[i]=Math.max((a[i]+a[i-1]+a[i-2]+b[i-3]-dp[i-3]),((a[i]+a[i-1]+b[i-2]-dp[i-2])));
                dp[i]=Math.max(dp[i],a[i]+b[i-1]-dp[i-1]);
            }
        }
        System.out.println(dp[n-1]);
        }
    }

}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <cmath> 
#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm> 

using namespace std;

int a[100010]; 
long long dp[100010]; 

int main()
{ 

    int z;
    for (scanf("%d",&z);z;--z) 
    {
        int n;
        scanf("%d",&n); 
        for (int i = 0; i < n; ++i) 
        { 
            scanf("%d",a + i);
        }
        long long sum = 0; 
        dp[n] = dp[n + 1] = dp[n + 2] = 0; 
        for (int i = n - 1; i >= 0; --i)
        { 
              sum += a[i]; 
              dp[i] = sum - min(min(dp[i + 1], dp[i + 2]), dp[i + 3]); 
         }
        printf("%lld\n",dp[0]); 
    }
    return 0; 
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long maximum(long x, long y, long z) {
    long h;
    h = x;
    if (y>h) {
        h=y;
    }
    if (z>h) {
        h=z;
    }
    return h;
}
long count_stack(long a[], int n) {
    long i,k1,k2,k3;
    long sum[n+1];
    long dp[n];
    sum[n]=0;
    for (i=(n-1);i>=0;i--) {
        sum[i]=sum[i+1]+a[i];
        dp[i] = sum[i];
    }
    
    for (i=(n-4);i>=0;i--) {
        k1 = sum[i+1] - dp[i+1] + a[i];
        k2 = sum[i+2] - dp[i+2] + a[i] + a[i+1];
        k3 = sum[i+3] - dp[i+3] + a[i] + a[i+1] + a[i+2];
        dp[i] = maximum(k1,k2,k3);
    }
    return dp[0];
}
void read_stack() {
    long max;
    long total = 0;
    int n,i;
    scanf("%d", &n);
    long a[n];


    for (i=0;i<n;i++) {
        scanf("%ld", &a[i]);
        total = total + a[i];
    }

    if (n>3) {
        max = count_stack(a,n);
    }else {
        max = total;
    }

    printf("%ld\n",max);
    
}

int main() {
    int t,i;
    scanf("%d", &t);

    for (i=0;i<t;i++) {
        read_stack();
    }
         
    return 0;
}

{"mode":"full","isActive":false}