Array Dynamic Programming Greedy
Learner Level

Implement the maximumProfitSingleTransaction method that returns the best stock profit using at most one buy and one sell.

The input contains an array prices and its length size. Each value represents the stock price on that day.

Your task is to return the maximum profit possible by buying once and selling once later. You must buy before you sell. If no profitable transaction is possible, return 0.

Example 1
Input:
prices (int[]) = [7,1,5,3,6,4]
size (int) = 6
Return:
(int) 5
Example 2
Input:
prices (int[]) = [7,6,4,3,1]
size (int) = 5
Return:
(int) 0
Example 3
Input:
prices (int[]) = [1,2]
size (int) = 2
Return:
(int) 1

Scan the prices from left to right while keeping the lowest buying price seen so far.

For each day, treat that day as a possible selling day. The profit is the current price minus the lowest earlier price. Update the best profit whenever this value is larger.

If prices keep decreasing, the best profit remains 0 because it is better not to make a transaction.

Pseudocode:

function maximumProfitSingleTransaction(prices, size):
    if size == 0:
        return 0
    minPrice = prices[0]
    bestProfit = 0
    for i from 1 to size - 1:
        profit = prices[i] - minPrice
        bestProfit = max(bestProfit, profit)
        minPrice = min(minPrice, prices[i])
    return bestProfit
Run your code to see the result.