Dark Mode

511 views

8 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

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