Title:
Best Time to Buy and Sell Stock
Link to LeetCode:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Specification:
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction
(i.e., buy one and sell one share of the stock),
design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Examples:
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation:
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Initial Code and Signature:
public interface ProfitMaximizer {
public int maxProfit(int[] prices);
}
Algorithm:
Run-Time Analysis:
GitHub Project:
Code:
/**
*
* @author Mahsa Sadi
*
* @since 2020 - 03 - 30
*
* License: Creative Commons
*
* Copyright by Mahsa Sadi
*
*/
public class ProfitMaximizerV1 implements ProfitMaximizer {
/**
* Problem: Best Time to Buy and Sell Stock
*
* Description:
* Say you have an array for which the ith element is the price of a given stock on day i.
* If you were only permitted to complete at most one transaction
* (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
* Note that you cannot sell a stock before you buy one.
*
*
* Solution:
* 1- Go to the end of array.
* 2- Find daily fluctuation for each day
* (i.e, the difference between today's and tomorrow's price).
* 3- Find maximum accumulative fluctuation starting from each day.
* (i.e, maximum ( daily fluctuation for the day, and daily fluctuation for the day + maximum accumulative fluctuation starting from the next day).
*
*
* 4- Return maximum accumulative fluctuation from among all the days.
*/
int [] dailyVariation;
int [] maxAccumulativeVariation;
int maxProfit;
boolean maxSet = false;
@Override
public int maxProfit(int[] prices) {
// TODO Auto-generated method stub
dailyVariation = new int [prices.length];
maxAccumulativeVariation = new int [prices.length];
if (prices.length == 0)
return 0;
for (int i = prices.length - 2; i >= 0; i--)
{
dailyVariation [i] = prices [i+1] - prices [i];
if (! maxSet)
{
maxAccumulativeVariation [i] = dailyVariation [i];
maxProfit = maxAccumulativeVariation [i];
maxSet = true;
}
else
{
maxAccumulativeVariation [i] = Math.max(dailyVariation [i], dailyVariation [i] + maxAccumulativeVariation [i+1]);
maxProfit = Math.max(maxProfit, maxAccumulativeVariation [i]);
}
}
if ( maxProfit > 0 )
return maxProfit;
else
return 0;
}
}