Why doesn't greedy approach work for following problem but the solution provided in the editorial does?

Question

Problem Statement:

Alexa has two stacks of non—negative integers, stack A = [a0,a1, . . . ,an_1] and stack B = [b0, b1, . . . ,bm_1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer given at the beginning of the game. Nick's fine/score is the total number of integers he has removed from the two stacks. Given A, B, and m for g games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified)

Link to the problem: https://www.hackerrank.com/contests/university-codesprint-2/challenges/game-of-two-stacks

My solution(greedy approach):

1. Pick(pop) the smallest element between the one present on top of the stack A and the other present on top of the stack B. Increment sum by the value of popped element and total(number of ints) by 1.
2. Repeat 1 until either sum becomes greater than asked or one of the two stacks get empty.
3. If one of the two stacks get empty then pop ints from the other stack until the current sum exceeds the asked limit.

Editorial solution:

This problem can be solved in linear time. We'll begin by taking as many integers as possible from stack A without exceeding the sum. Once we've done this we'll start taking integers from B, but whenever the sum becomes larger than the limit, we'll put integers back into stack A. Make sure to update the answer (the number of integers) as the traversal through stack B takes place. Break the loop when you have put back all integers that was taken from A and it's not possible to take any more integers from B.

Please explain where am I getting wrong and what is the intuition behind the editorial solution?

Answer 1

Consider the case where the target is 6, A is [2, 2, 2] and B is [3, 1, 1, 1]. The solution here is 4 achieved by using all of B, but your solution gives 3.

In general greedy algorithms will not yield optimal results in cases where you are supposed to look into the future.

To answer the second part of the question: the editorial description is incomplete. The important step that the description misses is to update the answer only when you have improved it. The reason this works is the following: you can represent each game state as two numbers: the number of values taken from A (call it x) and the number of values taken from B (call it y). We can call a state (x, y) valid if summing the top x values of A and top y values of B does not exceed some target. We can call a state (x, y) maximal if (x, y) is valid but neither (x + 1, y) nor (x, y + 1) are valid. The key point is the when we maximize x + y over valid states then (x, y) must be maximal. So we can reduce the problem to maximizing the sum of the maximal states and their are at most min(size(A), size(B) of those.

The editorial solution then is very simple: enumerate all the maximal positions in the following way: start by finding x such that (x, 0) is maximal. To get the next step, increment y and keep decrementing x until (x, y) is valid: it will clearly also be maximal. Stop when y is too big for (0, y) to be valid. You then take this list of maximal (x, y) pairs (and you will have all of them) and take the max of x + y.

The editorial solution happens to fuse the "enumerate the maximal states" and "take the max of their sums" steps, but this is an optimization that does not change its complexity.