Longest Text Producible in Editor

I saw an unsolved problem at http://intearview.com:

Problem

You are provided with four possible operations that can be done on the editor(each operation requires 1 keyboard hit)

1. A 
2. Ctrl+A 
3. Ctrl+C 
4. Ctrl+V

Now you can hit the keyboard N times and you need to find the maximum number of A's that can be printed. Also print the sequence of keyboard hits.

Algorithm

The first intuition on seeing this problem is we should use dynamic programming, as this problem has a clear structure of sub-problems. A straightforward trial is to distinguish different cases by the last operation. Nevertheless, difficulty arises when the last operation is Ctrl+V and the second last operation is not Ctrl+C.

In order to solve this problem, we have to further dissect the properties of an optimal edit sequence:

1. Ctrl+A always immediately precedes Ctrl+C, otherwise it cannot be optimal.
2. If a Ctrl+V follows an A, it is safe to push Ctrl+A backward to bypass A.
3. If a combo Ctrl+A Ctrl+C precedes an A, it is better to push the combo forward to bypass A. That is the original edit sequence cannot be optimal.

In summary, an optimal edit sequence can be shaped in a normal form, in which Ctrl+V's are grouped together, and a combo  Ctrl+A Ctrl+C immediately precedes each group.

As a consequence, if we denote the longest sequence of n operations by C(n), the recursion can be expressed as:
$$C(n)  = max(1+ C(n-1), max_{i}((i+1)\times C(n-2-i)))$$
in which \(1+C(n-1)\) is for the case when the last operation is A, and the latter part is for the case when a continuous block of Ctrl+V is at the end of the optimal edit sequence. Since we don't know the optimal size of the block, we have to do a linear scan which amounts to an algorithm of \(O(n^2)\)

Code

static String[] OPERATIONS = {"A", "Ctrl+A", "Ctrl+C", "Ctrl+V"};

int longestText(int n) {
  assert n > 0;
  int[] length = new int[n + 1];
  length[0] = 0;
  length[1] = 1;

  int[] optBlockSizes = new int[n+1]; // optimal size of Ctrl+V block ending at each position
  optBlockSizes[1] = 0; // no Ctrl+V block, i.e., A

  for (int i = 2; i < n+1; i++) { // for each length of edit sequence
    int len = length[i-1] + 1;
    optBlockSizes[i] = 0; // i.e., A
    for (int j = 1; j < i-2; j++) { // for each size of Ctrl+V block
     int newLen =  (j+1)*length[i-2-j];
     if (newLen > len) {
       len = newLen;
       optBlockSizes[i] = j;
     }
    }
  }
   
  // print the edit sequence 
  printEditSequence(optBlockSizes);

  return length[n];
}

void printEditSequence(int[] pastBlocks) {
   // the array is [0,n], with the first element useless
   int n = pastBlocks.length - 1;
   String[] editSequence = new String[n+1];
   printEditSequence(editSequence, pastBlocks, n);
}

// last is the largest unprocessed element index
void printEditSequence(String[] sequence, int[] blocks, int last) {
   if (last == 0) {// print sequence[1:n];
     for (int i = 1; i < sequence.length-1; i++) {
       System.out.print(sequence[i]+", ");
     }
     System.out.println(sequence[sequence.length-1]);
   }
   else {
     if (blocks[last] == 0) {
       sequence[last] = "A";
       printEditSequence(sequence, blocks, last-1);
     }
     else {
       int blockSize = blocks[last];
       for (int i = last; i > last - blockSize; last--) {
         sequence[i] = "Ctrl+V";
       } 
       sequence[last-blockSize-1] = "Ctrl+A";
       sequence[last-blockSize] = "Ctrl+C";
       printEditSequence(sequence, blocks, last-blockSize-2);
     }
   }
}