**π‘ Problem Formulation:** In stock trading, the challenge is to maximize profit by determining the best times to buy and sell stock. Given a list of stock prices where the index represents the day, we seek a Python program that can find the maximum potential profit. For example, given the input `[7,1,5,3,6,4]`

, the desired output is `5`

, achieved by buying at price 1 and selling at price 6.

## Method 1: Brute Force

This method involves comparing the price of each day with every subsequent day to find the maximum possible profit. While this method guarantees finding the maximum profit, its time complexity is O(n^2), making it impractical for large datasets.

Here’s an example:

def maxProfit(prices): max_profit = 0 for i in range(len(prices)): for j in range(i+1, len(prices)): max_profit = max(max_profit, prices[j] - prices[i]) return max_profit print(maxProfit([7,1,5,3,6,4]))

Output: `5`

The function `maxProfit`

iterates through each price and compares it with every other price that comes after it to calculate the profit, updating `max_profit`

whenever a higher profit is found.

## Method 2: Peak Valley Approach

By identifying valleys (lowest points) and peaks (highest points) in the stock prices, we can accumulate profit by buying at valleys and selling at peaks. This is more efficient than brute force with O(n) time complexity.

Here’s an example:

def maxProfit(prices): i, max_profit = 0, 0 while i < len(prices) - 1: # Find the next valley while i = prices[i + 1]: i += 1 valley = prices[i] # Find the next peak while i < len(prices) - 1 and prices[i] <= prices[i + 1]: i += 1 peak = prices[i] max_profit += peak - valley return max_profit print(maxProfit([7,1,5,3,6,4]))

Output: `7`

In the `maxProfit`

function, valleys and peaks are identified through a while loop. Profit is accumulated by subtracting the value at valley indices from peak indices.

## Method 3: Simple One-Pass

This method involves a single pass through the list of prices, keeping track of the minimum price to date and the maximum profit that can be made if sold at the current price.

Here’s an example:

def maxProfit(prices): min_price, max_profit = float('inf'), 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit print(maxProfit([7,1,5,3,6,4]))

Output: `5`

The function `maxProfit`

keeps updating the `min_price`

and `max_profit`

as it iterates through the list only once, resulting in an efficient algorithm with O(n) complexity.

## Method 4: Dynamic Programming

Dynamic Programming can be used to find the maximum profit by constructing a table where each entry contains the maximum profit up until that day. This method avoids recalculating results and optimizes for time, but uses extra space.

Here’s an example:

def maxProfit(prices): n = len(prices) if n <= 1: return 0 max_diff, max_profit = 0, [0] * n for i in range(1, n): max_diff = max(max_diff, prices[i] - prices[i-1]) max_profit[i] = max(max_profit[i-1], max_diff) return max_profit[-1] print(maxProfit([7,1,5,3,6,4]))

Output: `5`

By maintaining an array `max_profit`

, the function calculates the maximum profit continuously without redundancy. It is more space-heavy due to the auxiliary array usage.

## Bonus One-Liner Method 5: Functional Approach

Leveraging Python list comprehensions and built-in functions, we can find the maximum profit with a one-liner that is elegant but may be less readable.

Here’s an example:

print(max(j-min(prices[:i+1]) for i,j in enumerate(prices)))

Output: `5`

This functional one-liner iterates through the prices while keeping track of the minimum price up to the current day and the best profit possible if selling on the current day. It’s a compact and Pythonic approach but lacks clarity for larger codebases.

## Summary/Discussion

**Method 1: Brute Force.**This method is straightforward and guarantees a solution, but it is highly inefficient and impractical for large lists of stock prices due to its O(n^2) time complexity.**Method 2: Peak Valley Approach.**This method improves on efficiency with an O(n) time complexity and is suitable for cases where the stock prices have multiple peaks and valleys to capitalize on.**Method 3: Simple One-Pass.**Offers an elegant and efficient solution with O(n) time complexity, reducing operations by keeping track of ongoing minimum prices and maximum profits.**Method 4: Dynamic Programming.**Optimizes on time by storing interim profits, but at the cost of additional space, making it less optimal for memory-constrained environments.**Method 5: Functional Approach.**The compact and Pythonic one-liner is suitable for quick calculations but sacrifices readability and may not be the best for maintainability.