Back to Sliding Window
Easy
Best Time to Buy and Sell Stock
You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Examples
Input:prices = [7,1,5,3,6,4]
Output:5
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Input:prices = [7,6,4,3,1]
Output:0
In this case, no transactions are done and the max profit = 0.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 10^4
Approach
Use two nested loops to evaluate every possible transaction. The outer loop selects the buy day, and the inner loop selects the sell day (which must be after the buy day). Calculate the profit for each pair and keep track of the maximum profit.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach is highly inefficient and will likely result in a Time Limit Exceeded (TLE) error for large arrays.
Solution.java
class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { int profit = prices[j] - prices[i]; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; }}