MaximumRange | Topcoder Archive

Problem Statement

Cat Noku was given a calculator for his birthday. The calculator is very simple. It can only store a single variable. The variable is called X and its initial value is 0. The calculator has only two buttons: + and -. Pressing + increments X by 1 and pressing - decrements X by 1. For example, if X is 4 and Noku presses +, X is incremented to 5.

A string of '+' and '-' characters can be seen as a sequence of instructions to press the corresponding buttons. The range of such a sequence of instructions is the difference between the largest and the smallest value stored in X while executing that sequence of instructions, in order.

For example, the range of "+++++++" is 7: the largest value of X is 7 (at the end) and the smallest value is 0 (in the beginning). The range of "---" is 3: maximum is 0, minimum is (-3), their difference is 0 - (-3) = 3. The range of "+-+-+-" is 1. The range of an empty sequence of instructions is 0.

Noku's calculator came with a piece of paper that contained a String s. Each character of s was either '+' or '-'. Noku will choose and execute any (not necessarily contiguous) subsequence of these characters. Help him do so in a way that maximizes the range of the executed sequence.

Compute and return the maximal range of a subsequence of the String s.

Definition

Class:: MaximumRange
Method:: findMax
Parameters:: String
Returns:: int
Method signature:: int findMax(String s)
(be sure your method is public)

Constraints

s will contain between 1 and 2,500 characters, inclusive.
Each element of s will be '+' or '-'.

Examples

```
"+++++++"
```
```
Returns: 7
```
Cat Noku should choose the entire string s. As we saw in the problem statement, the range of "+++++++" is 7, and clearly this is the most we can get.
```
"+--+--+"
```
```
Returns: 4
```
One optimal solution is to skip the fourth instruction (the '+' in the middle of s). Thus, the sequence of button presses will be "+----+". The value of X will change as follows: 0,1,0,-1,-2,-3,-2. The maximum number we see is 1 while the minimum number is -3, so the range is 1 - (-3) = 4.
```
"++++--------"
```
```
Returns: 8
```
```
"-+-+-+-+-+-+"
```
```
Returns: 6
```
```
"+"
```
```
Returns: 1
```

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.