Solution to Problem 3: Gotta Max Profits

Another way of the stating the problem is: determine the maximum value subarray from the array of “crude” stock price changes. This is reducible to the maximum value subarray problem (oh yeah!).

There are three known ways (specific to my knowledge thus far) of solving this problem:

  • brute-force:  list all n(n-1)/2 (“n choose 2”) possible subarrays and determine which subarrray has the maximum value. O(n^2) running time.
  • divide-and-conquer: there’s a divide and conquer algorithm that runs in O(nlogn) time. It’s kind of cool but not as fast as we’d want it to be.
  • dynamic programming: this solution runs in O(n) time. What would we do without dynamic programming?

Below is the solution (using dynamic programming) to the maxSub array problem in python:

Recurrence relation for maxSub array problem

Given a sequence of n real numbers A(1) \ldots A(n), determine a contiguous subsequence A(i) \ldots A(j) for which the sum of elements in the subsequence is maximized.

For any i and j where 1 <= i <= j <= n
M(j) = Maximum sum over all windows ending at j.

M(j) = max \{ M(j-1) + A[j], A[j] \}. So either we extend the optimal window ending at j or start a fresh window with A[j].

Chao!

Problem 3: Gotta Max Profits

I’m a determined and ferocious trader on wall street. I only care about maximizing profits. An adaptive manipulator, I’m always the first person to react to (or rather to help my company adapt to) changes in the rules of the wall street money game. Yesterday, some rules pertaining to profits displays (on the floor of the main market) got changed.

Hitherto, maximum profits made by my company were displayed on the floor in a simple and intuitive way. So the only thing we needed to do to keep track of our max profits was to pipe the displayed maximum profits to our wall street data repository. But starting today, no maximum profits will be displayed. Only “crude” stock changes will be displayed. For example, the stock changes for the day (collected each hour) might look like this: [-2, 11, -4, 13, -5, 2].

Now I have to make some algorithm to compute the maximum profits I made during the day. For example, the maximum profit (from the data set above) is 20 over the subarray [11,-4,13].

Can you help construct an algorithm to solve this problem? I’m actually a good trader I promise.

Solution to Problem 2: Stripping Down My Luggage

The interesting thing about this problem is that there are so many ways to solve this problem. I’d recommend solving this problem by hand, no matter the algorithm you intend to use. You shouldn’t have to solve this problem via code.

Some methods you could use to solve this problem:

  • Easy brute force
  • dynamic programming (notice this problem is reducible to the Knapsack problem)
  • inspection

Anyways, my solution to the problem that fits all selected items in the 3kg remaining space and maximizes the total Preference index is to select the following
items:

Item Weight Preference
WW2 Galilean binoculars 0.5kg 5
Bufferfly knife 0.5kg 2
Camera 0.5kg 4
Laptop 1.5kg 6

Sum of selected item weights = 3.0kg
Sum of item preferences = 17

This problem is really easy but the point was to introduce you to the Knapsack problem.