Title:

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:

1. Go to the end of array.
2. Find daily fluctuation for each day.
(i.e, the difference between tomorrow's price and today'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 + maxmimum accumulative fluctuation starting from the next day.)
4. Return maximum accumulative fluctuation from among all the days.

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; } } ```