Problem Statement: You are given an array of prices where prices[i] is the price of a given stock on an 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.

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

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are
done and the max profit = 0.
```

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach Optimal Approach
Brute Force Approach
Algorithm / Intuition

Intuition: We can simply use 2 loops and track every transaction and maintain a variable maxPro to contain the max value among all transactions.

Approach

• Use a for loop of ‘i’ from 0 to n.
• Use another for loop of j from ‘i+1’ to n.
• If arr[j] > arr[i] , take the difference and compare  and store it in the maxPro variable.
• Return maxPro. Code
``````
#include<bits/stdc++.h>
using namespace std;

int maxProfit(vector<int> &arr) {
int maxPro = 0;
int n = arr.size();

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
maxPro = max(arr[j] - arr[i], maxPro);
}
}
}

return maxPro;
}

int main() {
vector<int> arr = {7,1,5,3,6,4};
int maxPro = maxProfit(arr);
cout << "Max profit is: " << maxPro << endl;
}
```
```

Output:

Max profit is: 5

``````
import java.util.*;
public class Main {
public static void main(String[] args) {
int arr[] = {7,1,5,3,6,4};
int maxPro = maxProfit(arr);
System.out.println("Max profit is: " + maxPro);
}

static int maxProfit(int[] arr) {
int maxPro = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i]) {
maxPro = Math.max(arr[j] - arr[i], maxPro);
}
}
}
return maxPro;
}
}
```
```

Output:

Max profit is: 5

``````
from typing import List

def maxProfit(arr: List[int]) -> int:
maxPro = 0
n = len(arr)

for i in range(n):
for j in range(i + 1, n):
if arr[j] > arr[i]:
maxPro = max(arr[j] - arr[i], maxPro)

return maxPro

if __name__ == "__main__":
arr = [7, 1, 5, 3, 6, 4]
maxPro = maxProfit(arr)
print("Max profit is: ", maxPro)
```
```

Output:

Max profit is: 5

Complexity Analysis

Time complexity: O(n^2)

Space Complexity: O(1)

Optimal Approach
Algorithm / Intuition

Intuition: We will linearly travel the array. We can maintain a minimum from the start of the array and compare it with every element of the array, if it is greater than the minimum then take the difference and maintain it in max, otherwise update the minimum.

Approach:

• Create a variable maxPro and store 0 initially.
• Create a variable minPrice and store some larger value(ex: MAX_VALUE) value initially.
• Run a for loop from 0 to n.
• Update the minPrice if it is greater than the current element of the array
• Take the difference of the minPrice with the current element of the array and compare and maintain it in maxPro.
• Return the maxPro. Code
``````
#include<bits/stdc++.h>
using namespace std;

int maxProfit(vector<int> &arr) {
int maxPro = 0;
int n = arr.size();
int minPrice = INT_MAX;

for (int i = 0; i < arr.size(); i++) {
minPrice = min(minPrice, arr[i]);
maxPro = max(maxPro, arr[i] - minPrice);
}

return maxPro;
}

int main() {
vector<int> arr = {7,1,5,3,6,4};
int maxPro = maxProfit(arr);
cout << "Max profit is: " << maxPro << endl;
}
```
```

Output: Max profit is: 5

``````
import java.util.*;

public class Main {

public static void main(String[] args) {
int arr[] = {7,1,5,3,6,4};

int maxPro = maxProfit(arr);
System.out.println("Max profit is: " + maxPro);

}
static int maxProfit(int[] arr) {
int maxPro = 0;
int minPrice = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
minPrice = Math.min(minPrice, arr[i]);
maxPro = Math.max(maxPro, arr[i] - minPrice);
}
return maxPro;
}
}
```
```

Output: Max profit is: 5

``````
def maxProfit(arr):
maxPro = 0
minPrice = float('inf')
for i in range(len(arr)):
minPrice = min(minPrice, arr[i])
maxPro = max(maxPro, arr[i] - minPrice)
return maxPro

arr = [7, 1, 5, 3, 6, 4]
maxPro = maxProfit(arr)
print("Max profit is:", maxPro)
```
```

Output: Max profit is: 5

Complexity Analysis

Time complexity: O(n)

Space Complexity: O(1)

Video Explanation