Canadian Informatics Workshop 2025: Day 1, Problem 2

Alice and Bob are playing a game with a chocolate bar. Initially, the chocolate bar consists of ~N~ connected chocolate squares in a line, where ~A_i~ represents the tastiness of the ~i~-th square. Each player takes turns splitting the bar of chocolate, with Alice going first.

For Alice, in a single split operation she can choose any connected piece of chocolate squares and split it into two separate pieces. For Bob, in a single split operation he can choose one of the two connected pieces of chocolate resulting from Alice's split on the previous turn and split his chosen piece into 2 separate pieces. If such a split operation cannot be performed by Bob, his turn is skipped.

Before the start of each player's turn, Alice can choose whether she wants to eat a connected piece of chocolate on the table, ending the game.

Alice's goal is to maximize the sum of tastiness of her chocolate bar, while Bob's goal is to minimize the sum of tastiness that Alice gets. Find the maximum sum of tastiness that Alice can achieve.

Input Specification

The first line of input will consist of a single integer ~N~ (~1\leq N\leq 600~), the number of chocolate squares in the initial bar.

The second line will consist of ~N~ space-separated integers ~A_1, \ldots, A_N~ (~-10^6\leq A_i\leq 10^6~), the tastiness of the chocolate squares.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~
3 marks	~1 \le N \le 8~
7 marks	~1 \le N \le 200~
15 marks	~1\leq N\leq 600~

Output Specification

Output a single integer, the maximum sum of tastiness that Alice can achieve.

Sample Input

4
1 2 -4 4

Sample Output

4

Explanation for Sample Output

Alice will split the bar into ~[1, 2, -4]~ and ~[4]~, then eat the piece with tastiness ~4~. It can be shown that ~4~ is the maximum tastiness she can achieve.