Problem Statement :-
You are given an array prices where prices[i]
is the price of a given stock on the ith 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.
Example 1:
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Solution 1
by using 2 loops we can easily solve this problem. 1st loop buys the stock, the second loop sells the stock. by each selling, we maintain the max profit.
lets understand this step by step,
step-1 initialize a variable maxProfit=0
.
step-2 run a loop from i=0
to prices.length
.
1. initialize
buyPrice = prices[i]
2. run another loop fromj=i+1
toprices.length
.1. initialize
sellPrice = prices[j]
2. ifsellPrice
>buyPrice
then,1.calculate the profit.
profit = sellPrice - buyPrice
2. ifprofit > maxProfit
then,update themaxProfit
.
maxProfit = profit
step-3 end.
have a at look this pic for a better understanding.
Java
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for(int i=0; i<prices.length;i++){
int buyPrice = prices[i];
for(int j=i+1;j<prices.length;j++){
int sellPrice = prices[j];
if(sellPrice > buyPrice){
int profit = sellPrice - buyPrice;
if(profit > maxProfit)
maxProfit = profit;
}
}
}
return maxProfit;
}
}
Time Complexity⏱️
we are running two loops then,
Time Complexity: O(n*n)
Space Complexity⛰️
we are not using any extra space then,
Space Complexity: O(1)
Solution 2
this problem can be solve by using kadane's algorithm with O(n) Time Complexity.
step-1 initialize three variables
buyPrice = prices[0]
,
sellPrice
,
maxProfit = 0
,
step-2 run a loop from i=1
to prices.length
and then,
1. initialize
sellPrice = prices[i]
2. ifsellPrice < buyPrice
then update thebuyPrice
,
buyPrice = sellPrice
.
3. calculate the profit.
profit = sellPrice - buyPrice
4. if
profit > maxProfit
then update themaxProfit
maxProfit = profit
step-3 end.
class Solution {
public int maxProfit(int[] prices) {
int buyPrice = prices[0];
int sellPrice;
int maxProfit = 0;
for(int i = 1; i<prices.length; i++){
sellPrice = prices[i];
if(sellPrice < buyPrice)
buyPrice = sellPrice;
int profit = sellPrice - buyPrice;
if(maxProfit < profit)
maxProfit = profit;
}
return maxProfit;
}
}
thank you for reading this article. if you find any mistake let me know in the comment section.
Top comments (0)