a) Describe a brute-force algorithm for computing the maximum jump in value as w
ID: 3915142 • Letter: A
Question
a) Describe a brute-force algorithm for computing the maximum jump in value as well
as identifying the specic buy and sell dates for this maximum jump. What is its running
time?
b) We will determine a divide-and-conquer approach to nding the best dates for buying
and selling the stocks as well as the value of the maximum prot. Fill in an appropriate action
for step (d) (seriously):
(a) Split the array in half
(b) Find the maximum jump and buy/sell dates entirely in the left half
(c) Find the maximum jump and buy/sell dates entirely in the right half
(d) ???
(e) Choose the overall maximum jump
(f) Prot!
c. For your step (d) above, what specic pieces of information do you need?
d. Write your complete divide and conquer algorithm for the stock market problem.
e. Give a recurrence relation for your algorithm, and solve it for an asymptotic running time.
"Computer scientist makes S0.38 a day working from home find out how!!!" A popular pastime of computer scientists (especially academics) is fantasizing about how to use our knowledge to get rich playing the stock market. The first advice one receives about playing with stocks is "buy low, sell high". Easier said than done. Suppose we have a set S-(s1, s2, . . . , sn} of integer values where si represents the price of a stock on day i. Given this historic price data, we wish to (retrospectively) find the best time to buy and sell the stock, which should be a contiguous interval with the highest jump in price. Example: S = {2, 10, 3,0,4,0,0,1, 3,3,9,0, 21, 15, 17,4) has a maximum jump of 21 if purchased on day i - 4 and sold on day j- 13.Explanation / Answer
1).Stock Single Sell Problem using Brute-force algorithm – O(n^2) Solution-
Objective: Given an array represents cost of a stock on each day.Describe a brute-force algorithm for computing the maximum jump in value as well as identifying the specic buy and sell dates for this maximum jump. What is its running time?
S={2,10,3,0,4,0,0,1,3,3,9,0,21,15,17,4} has a mazimum jump of 21 if purchaased on day i=4 and sold on day j=13.
Brute Force Algorithm
Use two nested loops. Taking one element at a time, consider outer loop value as buying date index and compare it with the every element in the inner loop which will be considered as selling index date. Keep track of the maximum. This will be the maximum profit.
Time Complexity: O(n^2)
PROGRAM:
public class StockSingleSellBruteForce {
public static void maxProfit(int [] prices){
int profit = -1;
int buyDate = prices[0];
int sellDate = prices[0];
for (int i = 1; i <prices.length ; i++) {
for (int j = i; j <prices.length ; j++) {
if(prices[j]>prices[i] && (prices[j]-prices[i]>profit)) {
profit = prices[j] - prices[i];
buyDate = i;
sellDate = j;
}
}
}
System.out.println("Maximum Profit: " + profit + ", buy day: " + buyDate +
", sell day: " + sellDate );
}
public static void main(String[] args) {
int prices[] = {2,10,3,0,4,0,0,1,3,3,9,0,21,15,17,4};
maxProfit(prices);
}
}
2: Divide and Conquer
APPROACH:
(a) Split the array in half
(b) Find the maximum jump and buy/sell dates entirely in the left half
(c) Find the maximum jump and buy/sell dates entirely in the right half
(d) ???
(e) Choose the overall maximum jump
(f) Prot!
c. For your step (d) above, what specic pieces of information do you need?
d. Write your complete divide and conquer algorithm for the stock market problem.
e. Give a recurrence relation for your algorithm, and solve it for an asymptotic running time.
1. The approach of Divide and Conquer is similar to Maximum Subarray Problem using Divide and Conquer.
2. First of all find out a subarray of the greatest sum. So, here we find two days for max profit (left index and right index).
3. Divide the problem into 2 parts, left half and right half.
Time Complexity: O(nlogn).
PROGRAM CODE:
public class StockSingleSellDandC {
public Result maxProfit(int [] prices, int start, int end){
if(start>=end){
return new Result(0,0,0);
}
int mid = start + (end-start)/2;
Result leftResult = maxProfit(prices,start,mid);
Result rightResult = maxProfit(prices,mid+1,end);
int minLeftIndex = getMinIndex(prices, start, mid);
int maxRightIndex = getMaxIndex(prices, mid, end);
int centerProfit = prices[maxRightIndex] - prices[minLeftIndex];
if(centerProfit>leftResult.profit && centerProfit>rightResult.profit){
return new Result(centerProfit,minLeftIndex,maxRightIndex);
}else if(leftResult.profit>centerProfit && rightResult.profit>centerProfit){
return leftResult;
}else{
return rightResult;
}
}
public int getMinIndex(int [] A, int i, int j){
int min = i;
for (int k = i+1; k <=j ; k++) {
if(A[k]<A[min])
min = k;
}
return min;
}
public int getMaxIndex(int [] A, int i, int j){
int max = i;
for (int k = i+1; k <=j ; k++) {
if(A[k]>A[max])
max = k;
}
return max;
}
public static void main(String[] args) {
StockSingleSellDandC m = new StockSingleSellDandC();
int prices[] = {2,10,3,0,4,0,0,1,3,3,9,0,21,15,17,4};
int start = 0;
int end = prices.length-1;
Result result = m.maxProfit(prices,start,end);
System.out.println("Maximum Profit(Divide & Conquer): " +result.profit + ", buy day: " + result.buyDate +
", sell day: " + result.sellDate);
}
}
class Result{
int profit=0;
int buyDate=0;
int sellDate=0;
public Result(int profit, int buyDate, int sellDate){
this.profit = profit;
this.buyDate = buyDate;
this.sellDate = sellDate;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.