A function f defined on stacks of integers satisfies the following properties.…
2005
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
- A.
6
- B.
4
- C.
3
- D.
2
Attempted by 107 students.
Show answer & explanation
Correct answer: C
Definition: f(∅) = 0, and for any stack S and integer i, f(push(S, i)) = max(f(S), 0) + i.
Start with the empty stack: f = 0.
Push 2 (bottom): f = max(0,0) + 2 = 2.
Push -3: f = max(2,0) + (-3) = 2 - 3 = -1.
Push 2: f = max(-1,0) + 2 = 0 + 2 = 2.
Push -1: f = max(2,0) + (-1) = 2 - 1 = 1.
Push 2 (top): f = max(1,0) + 2 = 1 + 2 = 3.
Final answer: f(S) = 3.
A video solution is available for this question — log in and enroll to watch it.