Calculate Max Profit - Buy and Sell Stocks Multiple Times - Leet Code Solution
August 27, 2020
Problem Statement
Say you have an array prices for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Examples
Input: [7,1,5,3,6,4]
Output: 7
Explanation:
- buy on day-2, sell on day-3. Profit (5-1) = 4
- buy on day-4, sell on day-5. Profit (6-3) = 3
Solution (Simple)
Lets try a brute force algorithm. Since we know the constraint that we need to buy the stock before selling it.
- We can traverse the array.
- For every price, we can find if there is any following high price.
- If high price exists. Calculate profit, and run same algorithm on remaining array.
Code
private int maxProfit_simpleRecursive(int[] prices, int startIndex) {
if (startIndex >= prices.length) {
return 0;
}
int maxProfit = 0;
for (int i=startIndex; i<prices.length; i++) {
int max = 0;
for (int j=i+1; j<prices.length; j++) {
//when can we sell
if (prices[j] > prices[i]) {
int profit = (prices[j] - prices[i]) + this.maxProfit_simpleRecursive(prices, j+1);
if (max < profit) {
max = profit;
}
}
}
if (maxProfit < max) {
maxProfit = max;
}
}
return maxProfit;
}
public int maxProfit_simple(int[] prices) {
return this.maxProfit_simpleRecursive(prices, 0);
}
Complexity
Above code runs in O(n^n)
.
A Better Solution
If we try to draw the input in some sort of graph or line chart. We can see some pattern.
If you look closely, we can keep track of low points, and following high point. And take a sum of such points. We can get the maximum profit.
In the above image, we can take following calculation:
Low-point=1, High-point=5, Profit=4
Low-point=3, High-point=6, Profit=3
Total Profit = 7
Code
public int maxProfit_better(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
int i=0;
int lowPrice = prices[i];
int highPrice = prices[i];
i++;
while (i < prices.length) {
//find low value
while (i < prices.length && prices[i-1] >= prices[i]) {
i++;
}
lowPrice = prices[i-1];
//find high value
while (i<prices.length && prices[i] >= prices[i-1]) {
i++;
}
highPrice = prices[i-1];
max += (highPrice - lowPrice);
}
return max;
}
Complexity
The code runs in O(n)
time as we are running loop n times only.
Better and Simple Solution
Above solution worked and is way faster than our first solution. Lets think more about the second solution. We are just finding low peak and high peak, finding difference and take it.
Instead, can we just take the difference if two consecutive prices are in increasing order. Yes, definitely.
Code
Lets look at the code:
public int maxProfit_better2(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
for (int i=1; i<prices.length; i++) {
if (prices[i] > prices[i-1]) {
max += (prices[i] - prices[i-1]);
}
}
return max;
}
Complexity
Its again O(n)
Similar Posts
Rotate Image - Leet Code Solution
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Three Sum Closest - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, find…
Add two numbers(reverse order) link list Problem - Leet Code Solution
Problem Statement You are given two non-empty linked lists representing two non…
What FAANG companies expect in their interview from candidates
Its every software engineer’s dream to work with the big FAANG companies…
Bubble Sort Algorithm
This is kind of preliminary technique of sorting. And, this is the first…
Latest Posts
System Design Interview Vocabulary Notes
In this post, we will see some of the frequently used concepts/vocabulary in…
Coding Interview - Facebook System Design Interview Types
System design interview is pretty common these days, specially if you are having…
Find the maximum sum of any continuous subarray of size K
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting - Build System Order Example
Graph Topological Sorting This is a well known problem in graph world…
Binary Tree - Level Order Traversal
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Four Sum - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, are…