recategorized by
660 views
2 votes
2 votes

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
recategorized by

1 Answer

Best answer
8 votes
8 votes
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
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,637 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
3
0 votes
0 votes
0 answers
4