Ph.D. Qual Study Assistant

1. The Problem

Given a sequence of `n` positive numbers `a_1, ..., a_n`, the goal is to find a subsequence that is strictly increasing and whose elements have the maximal possible sum.

For example, given `1, 101, 2, 3, 100, 4, 5`, the subsequence `1, 2, 3, 4, 5` has a sum of 15. The subsequence `1, 101` has a sum of 102. The optimal subsequence is `1, 2, 3, 100`, which is increasing and has a sum of 106.

2. The Idea: Dynamic Programming

This problem is a variation of the Longest Increasing Subsequence problem. We can use a similar dynamic programming approach. The key is to build up a solution by considering each element as the potential end of an optimal subsequence.

Let `MSIS[i]` be the maximum sum of an increasing subsequence that ends at index `i` (i.e., includes the element `a_i`).

• Base Case: For any element `a_i`, a subsequence consisting of only `a_i` itself is an increasing subsequence. So, we initialize `MSIS[i] = a_i` for all `i`.
• Recurrence Relation: To compute `MSIS[i]`, we must extend an existing increasing subsequence. We look at all previous elements `a_j` where `j < i`. If `a_j < a_i`, then `a_i` can extend the subsequence ending at `j`. The sum of this new subsequence would be `MSIS[j] + a_i`. We want the best such `j` to maximize this sum.

The final answer is not necessarily `MSIS[n-1]`, as the maximal sum subsequence could end at any position. The answer is the maximum value in the entire `MSIS` array after it has been fully computed.

3. The Algorithm

1. Create a 1D array, `MSIS`, of size `n`. Initialize `MSIS[i] = a_i` for each `i` from 0 to `n-1`.
2. Create a 1D array, `Path`, of size `n` to reconstruct the sequence. Initialize `Path[i] = -1`.
3. Iterate with `i` from 1 to `n-1`.
   • Iterate with `j` from 0 to `i-1`.
     • If `a_j < a_i` and `MSIS[j] + a_i > MSIS[i]`:
       Update `MSIS[i] = MSIS[j] + a_i`.
       Record the predecessor: `Path[i] = j`.
4. Find the index `max_index` where `MSIS[max_index]` is the maximum value in the `MSIS` array.
5. The maximum sum is `MSIS[max_index]`. Reconstruct the subsequence by backtracking from `max_index` using the `Path` array.

4. Complexity Analysis

Time Complexity: O(n²)

The algorithm uses two nested loops. The outer loop runs `n-1` times, and the inner loop runs up to `n-1` times. The operations inside the loops are constant time. This leads to a time complexity of O(n²).

Space Complexity: O(n)

We use two 1D arrays, `MSIS` and `Path`, both of size `n`, which requires O(n) auxiliary space.