1. Overview
In this tutorial, we’ll discuss the problem of finding the Maximum single-sell profit in an array. We’ll present a naive approach and then improve it to obtain a better solution.
2. Defining the Problem
Suppose we’re concerned with a product. In advance, we know the prices of this product over the next days. The price of the ith day is denoted as . Hence, we’re given an array called of size .
We must choose two days from this array. On the first day, we’ll buy the product, and on the second, we’ll sell it. We need to make the maximum profit from this operation.
In other words, we need to find the maximum value of , such that .
3. Naive Approach
First, we’ll explore the naive approach. Let’s take a look at its implementation:
algorithm MaxSingleSellProfitNaive(P, n):
// INPUT
// P = the prices array
// n = the size of the prices array
// OUTPUT
// maximum single-sell profit, buy day, and sell day
Answer <- 0
buyDay <- 0
sellDay <- 0
for i <- 1 to n:
for j <- i to n:
if Answer <= P[j] - P[i]:
Answer <- P[j] - P[i]
buyDay <- i
sellDay <- j
return Answer, buyDay, sellDay