In Java

Problem Description

In this project, our input is an array of doubles, where each entry A $[$i$]$ denotes the price

of a stock $($or some other asset$)$ on the ith day. 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,$ and so on$.$

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$ numbers 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$).($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.$)$:

The optimal solution for input.txt is X$.$

Here, input.txt should be whatever the name of the given input file is$,$ and $x$

should be the actual optimal solution.

Your output must exactly match the format above, including letter capitalization

and punctuation marks.

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(nlogn)$ time. If you do not give a divide and conquer algorithm

for this project, you will get a $0.$ The entire point of this project is to design and

implement a divide and conquer algorithm, not just to get some solution that works.