We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
staticinttwoStacks(intx,int[]a,int[]b){intai=0;intbi=0;intcount=0;intsum=0;// move bi to the position where if only take elements from B, last element it can takewhile(bi<b.length&&sum+b[bi]<=x){sum+=b[bi];bi++;}bi--;// loop exits only when bi reaches end or sum > x; in both case bi should decreasecount=bi+1;while(ai<a.length&&bi<b.length){sum+=a[ai];if(sum>x){while(bi>=0){sum-=b[bi];bi--;if(sum<=x)break;}// if even no elements taken from B, but still sum greater than x, then a[ai] should not be chosen// and loop terminatesif(sum>x&&bi<0){ai--;break;}}count=Math.max(ai+bi+2,count);ai++;}returncount;}
The key point is that the order how each element is selected does not matter, which makes things complicated at the first galance. But if we consider through the final result, we should know that the problem is equals to that, to choose the maximum number of elements from each stack so that them sum is no greater than x. The finally selected elements come from either both stacks, either all from one stack. So let's start with assuption that all from stack B. Then everthing time try adding one element from A, if the total sum is greater than x, then we should reduce elements we took from B until the sum is no more than x which will form a valid way of selection. Keep trying until no more elements can be taken from A or B. We just need to keep track of the maximum number of total elements selected.
Game of Two Stacks
You are viewing a single comment's thread. Return to all comments →
My Java solution :
The key point is that the order how each element is selected does not matter, which makes things complicated at the first galance. But if we consider through the final result, we should know that the problem is equals to that, to choose the maximum number of elements from each stack so that them sum is no greater than x. The finally selected elements come from either both stacks, either all from one stack. So let's start with assuption that all from stack B. Then everthing time try adding one element from A, if the total sum is greater than x, then we should reduce elements we took from B until the sum is no more than x which will form a valid way of selection. Keep trying until no more elements can be taken from A or B. We just need to keep track of the maximum number of total elements selected.