Cerinta completa

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.

As an example, bricks are numbered . You can remove either , or . For your friend, your moves would leave the options of to elements from leaving for you (total score = ), or . In this case, it will never be optimal for your friend to take fewer than the maximum available number of elements. Your maximum possible score is , achievable two ways: first move and the second, or in your first move.

Function Description

Complete the bricksGame function in the editor below. It should return an integer that represents your maximum possible score.

bricksGame has the following parameter(s):

  • arr: an array of integers

Input Format

The first line will contain an integer , the number of test cases.

Each of the next pairs of lines are in the following format:
The first line contains an integer , the number of bricks in .
The next line contains space-separated integers $arr[i].

Constraints



Output Format

For each test case, print a single line containing your maximum score.

Sample Input

2
5
999 1 1 1 0
5
0 1 1 1 999

Sample Output

1001
999

Explanation

In first test case, you will pick 999,1,1. If you play in any other way, you will not get a score of 1001.
In second case, best option will be to pick up the first brick (with 0 score) at first. Then your friend will choose the next three blocks, and you will get the last brick.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

  /*
   * Complete the bricksGame function below.


   [1,3,4,5]
    1 4 8 13
   */
  static long bricksGame(int[] arr) {
    int n = arr.length + 1;
    for (int i = 0; i < arr.length / 2; i++) {
      int tmp = arr[i];
      arr[i] = arr[arr.length - i - 1];
      arr[arr.length - i - 1] = tmp;
    }
    long[] sums = new long[n];
    for (int i = 1; i < n; i++) {
      sums[i] = sums[i - 1] + arr[i - 1];
    }
    long[] dp = new long[n];
    dp[1] = sums[1];
    dp[2] = sums[2];
    dp[3] = sums[3];
    for (int i = 4; i < n; i++) {
      dp[i] = Math.max(
          sums[i] - dp[i - 1],
          Math.max(
              sums[i] - dp[i - 2],
              sums[i] - dp[i - 3]
          )
      );
    }
    return dp[n - 1];
  }

  private static final Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int t = Integer.parseInt(scanner.nextLine().trim());

    for (int tItr = 0; tItr < t; tItr++) {
      int arrCount = Integer.parseInt(scanner.nextLine().trim());

      int[] arr = new int[arrCount];

      String[] arrItems = scanner.nextLine().split(" ");

      for (int arrItr = 0; arrItr < arrCount; arrItr++) {
        int arrItem = Integer.parseInt(arrItems[arrItr].trim());
        arr[arrItr] = arrItem;
      }

      long result = bricksGame(arr);

      bufferedWriter.write(String.valueOf(result));
      bufferedWriter.newLine();
    }

    bufferedWriter.close();
  }
}

Scor obtinut: 1.0

Submission ID: 464604836

Link challenge: https://www.hackerrank.com/challenges/play-game/problem

Bricks Game