Assignment #3a: Stock Market Optimality

Problem Statement

The input is an array of positive numbers. Find two numbers a[i] and a[j] in the array such that j is greater than or equal to i and a[j]/a[i] is maximized. Notice that if the array represents a daily closing stock price, then what you are looking for is the optimal buying point (i) and selling point (j), so as to maximize your percentage gain.

Inputs

The inputs will be contained in a separate file. There will be one number Each line. Checking this is easily done using a stringtokenizer. You must get the file name(s) from command line argument(s). You may not make any assumptions about the size of the inputs; use array-doubling as needed, or read into an ArrayList (of Double) and then convert the ArrayList item by item into an array of double. Of course, you must report any bad lines in the input. After issuing a warning, skip the bad line, as if it never occurred.

What You Have To Do

There is a trivial brute-force algorithm to solve the problem. You will need to write code that uses this algorithm. You must then design a significantly faster recursive algorithm, and write code for that too. Significantly faster means that it has better Big-Oh performance; there is no credit if your second algorithm does not successfully produce a correct answer for all the inputs. Here is the function signature: 
public static int [ ] bestGain( double [ ] arr );
The return type is an array of two integers, representing the indexes i and j that are optimal. The recursive algorithm, which is likely to involve writing a private routine that is called by the above public routine makes use of the fact that the optimal buying/selling points are either:
  1. both in the first half;
  2. both in the second half; or,
  3. the buy is in the first half, but the sell is in the second half,
and the third case is easily computed by finding the lowest value in the first half and the highest value in the second half.

YOU MUST USE THIS RECURSIVE ALGORITHM, EVEN IF YOU CAN FIND A MORE EFFICIENT NON-RECURSIVE ALGORITHM.

Submission Details

Your submission should include
  1. your source code that implements the algorithms
  2. sample runs for both algorithms (the brute-force algorithm will not run on the larger inputs, so don't bother)
  3. an indication of how long each algorithm takes on the inputs that it runs on (use either the System.getCurrentTimeMillis both prior to and immediately following the call to the public driver,subtracting the results.
I will provide four good test cases of various sizes.

Due Date

This program is due on October 11.