MaximumRangeDiv2

SRM 715 · 2017-02-20 · by lg5293

SRM 715 · 2017-02-20 · by lg5293 · Brute Force, String Manipulation

Show categories

Class Name: MaximumRangeDiv2

Return Type: int

Method Name: findMax

Arg Types: (string)

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.

Constraints

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

Examples

"+++++++"
Returns: 7

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: 4

One optimal solution is to skip the 4th instruction. Thus, the sequence of button presses will be "+----+". The number we see after each button press is 1,0,-1,-2,-3,-2. The maximum number we see is 1, while the minimum number is -3, so their range is 4.

"++++--------"
Returns: 8

"-+-+-+-+-+-+"
Returns: 6

"+"
Returns: 1

Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MaximumRangeDiv2 with a public method int findMax(string s) · 65 test cases · 2 s / 256 MB per case