JumpingLevel | Topcoder Archive

Problem Statement

You are playing a computer game. The current level consists of N platforms, arranged from the left to the right and numbered 0 through N-1 in this order. Your character starts the level on platform 0. The level ends as soon as the character reaches platform N-1 for the first time. At the beginning of the game your score is 0.

You move by making jumps. You may jump only to the right. Each jump decreases your score by the distance you jumped. That is, a jump from platform x to platform y (where y > x) decreases your score by (y-x).

For each i between 1 and N-2, inclusive, there is a treasure chest on platform i. If and when your character jumps onto platform i, it automatically collects the treasure chest. You know that this treasure chest adds score[i] to your current score. But be careful: some of these values may be negative! Such treasure chests will decrease your score.

You are given the int[] score with N elements. Compute and return the maximum score that can be achieved at the end of the game.

Definition

Class:: JumpingLevel
Method:: maxScore
Parameters:: int[]
Returns:: int
Method signature:: int maxScore(int[] score)
(be sure your method is public)

Notes

The value N is not given explicitly. Instead, you can determine it by looking at the number of elements in score.
For your convenience, score contains elements that correspond to platforms 0 and N-1. These platforms don't contain any treasure chests, so the corresponding elements of score are always zero.

Constraints

score will contain between 2 and 50 elements, inclusive.
Each element of score will be between -1000 and 1000, inclusive.
score[0] will be 0.
score[ length(score)-1 ] will be 0.

Examples

```
{0, 0}
```
```
Returns: -1
```
The simplest possible level. There are no treasure chests, you just have to jump from platform 0 to platform 1 to finish the level. The jump will decrease your score by 1, so your final score will be -1.
```
{0, 1000, 1000, 0}
```
```
Returns: 1997
```
The optimal solution for this level: Jump from platform 0 to platform 1 (score becomes -1) and automatically collect the treasure chest there (score becomes 999). Jump from platform 1 to platform 2 (score becomes 998) and automatically collect the treasure chest there (score becomes 1998). Jump from platform 2 to platform 3 and finish the level (score becomes 1997).
```
{0, -1000, -1000, 0}
```
```
Returns: -3
```
These treasure chests decrease your score considerably. The optimal solution is to avoid them and finish the whole level by making one large jump from platform 0 straight to platform 3.

{0, 3, -1, 4, 1, -5, 9, 2, -6, 0}

Returns: 10

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.