"Picking Cards" challenge

I recently tried my hand at CodeSprint2 through Interview Street. Having not coded in quite some time, I wasn't surprised that I had difficulty writing optimized code, but on one problem in particular I can't find where I've gone wrong. I've compared my code to successful algorithms used by other programmers, and I don't see much difference. I tried in both Java and Ruby and hit a wall at the 4th test case with both (I'm just learning Ruby so thought it would be a fun exercise to try it - I tweaked my algorithm a little in the process).

The problem is Picking Cards and the description is here.

Code in Java:

```
import java.io.*;
import java.util.*;
import java.math.*;

public class Cards3 {

public Cards3()
{
}

public void run()
{
ArrayList cards = new ArrayList();
try{
/*
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input = reader.readLine();

StringTokenizer tokenizer = new StringTokenizer(input);
int T = Integer.parseInt(tokenizer.nextToken());
*/

DataInputStream reader = new DataInputStream(System.in);
int T = reader.readInt();
reader.readChar();
System.out.println("T = " + T);
//read in and test each subsequence
for(int i = 0; i();
}

reader.close();
}
catch (IOException e)
{
System.out.println("Can not read input.");
}
}

//computers the number of ways to pick up cards in currCards given that
//numPicked cards have already been picked up
public long numWays(ArrayList cardsLeft)
{
int numPicked = 0;
long numWays = 1;

//calculate until all cards are picked up
while(cardsLeft.size() >= 1)
{
//if we can't pick up the next card, we're at a dead end - no solutions
if(cardsLeft.get(0) > numPi

The immediate thing that jumps out to me is your use of an ArrayList for this. By continuously removing the first element, you force the array list to shift everything left one space each time (an O(n) operation assuming no underlying optimizations!)

Instead of removing from the array list (incurring an expensive shift), I would recommend that you keep an index.

while(cardsLeft.size() >= 1)
    {
        //if we can't pick up the next card, we're at a dead end - no solutions
        if(cardsLeft.get(0) > numPicked)
            return 0;

        // ...
        for(int i: cardsLeft)
        {   
             // ...
        }

        // ...

        cardsLeft.remove(0);
        // ...
    }

becomes

int cardIndex = 0;
    while(cardIndex  numPicked)
            return 0;
        // ...
        for(int i = cardIndex; i < cardsLeft.length(); ++i)
        {   
             // ...
        }
        // ...

        //cardsLeft.remove(0);
        ++cardIndex
        // ...
    }

StackExchange Code Review Q#8419, answer score: 3