Writing in language: C
In this project, our input is an a
ay of doubles, where each entry A[i] denotes the price of a
stock (or some other asset) on the ith day. So for example, if A = [5, 2, 3, 6, 1, 3] then this means
that the stock in question was worth 5 on day 0, it was worth 3 on day 2, etc. We will consider
buying the stock once and then later selling it once (of course we must sell the stock after we
have bought it). If we buy the stock on buyDay and we sell the stock on sellDay, then the goal is
to maximize our profit A[sellDay] – A[buyDay]. In the example above, the optimal solution is for
buyDay to be 1 (buying at the price A[1] = 2) and sellDay to be 3 (selling at the price A[3] = 6).
This gives us a profit of 4.
Stating the parameters formally:
● We must sell on a different day than we buy, and we must sell after we buy. In other
words, we must have buyDay < sellDay.
● This means that if A has <= 1 number in it, there is no feasible solution. This will affect
the base case of your algorithm!
● The return value should be the optimal profit (you don’t need to return the exact days
you are buying and selling). So in the example above, we would return 4.
● Your output should print the following to standard output (e.g., using printf() or
System.out.println(), etc.):
o The optimal solution for input.txt is X.
o Here, input.txt should be whatever the name of the given input file is, and X should
be the actual optimal solution.
This problem is not hard to get a solution that works using two nested for-loops (it runs in time
O(n^2)). We are wanting to improve this to a divide and conquer algorithm that runs in
O(n*log n) time.
You must provide a bash script named ‘project1.sh’ that will act similarly to a makefile.
In short, your bash script should contain the command to compile your code, and then on a
different line, it should contain the line to execute your code. There are several input files for
you to test your code on, and the bash script should take a command line argument specifying
which input file to run on. So, the command to execute your code should look like this:
bash project1.sh input.txt
There are no source files for this project. However there is a blank project1.sh file for you to fill
in as well as several input files to test your code with. Each input file contains a single price on
each line of the file. The first line should be index 0 of your a
ay, the second line should be
index 1, etc. We will test your code with all the provided input files, but we will also be testing
with some different input files that will be in the same format. Some of these files may be very
large (hundreds of thousands of entries).
Also, there is an example output.txt file for what your output should look like.
**Did the code give a divide and conquer algorithm that runs in O(n*log n) time that returns
the co
ect answer for all possible inputs?