The Gateway to Computer Science Excellence
+1 vote
137 views

A function f is defined on stack of integer satisfies the following properties .

f(empty) = 0 and f( PUSH(S,i) ) = max (f(S),0) + i   for all stacks S and integer i.

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top ,  Then what is f(S)?

  1. 6
  2. 4
  3. 3
  4. 2
in Programming by Veteran (74.6k points)
recategorized by | 137 views

1 Answer

+7 votes
Best answer
f is defined on a stack and its value changes on a push operation.

Initially f(S)=0 when no element is present and f(empty)=0 as defined in the question.These elements are to be pushed into the stack in the same sequence 2,-3,2,-1,2, Below is the formula.

f(PUSH(S,i)) = max (f(S),0)+i

After first push, 2, f(S)=max(0,0) + 2 = 2.

After second push, -3, f(S)=max(2,0) + −3 = −1

After third push, 2, f(S)=max(−1,0) + 2 = 2

After fourth push, -1, f(S)=max(2,0) + -1 = 1

After fifth push, 2, f(S)=max(1,0) + 2 = 3

Therefore the answer is (C) 3
by Junior (757 points)
selected by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,339 answers
198,449 comments
105,204 users