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 from`j=i+1`

to`prices.length`

.

1.initialize`sellPrice = prices[j]`

2.if`sellPrice`

>`buyPrice`

then,

1.calculate the profit.

`profit = sellPrice - buyPrice`

2.if`profit > maxProfit`

then,update the`maxProfit`

.

`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.if`sellPrice < buyPrice`

then update the`buyPrice`

,

`buyPrice = sellPrice`

.

3.calculate the profit.

`profit = sellPrice - buyPrice`

4.if`profit > maxProfit`

then update the`maxProfit`

`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.*

## Discussion (0)