.png)
Stock Buy and Sell (Multiple Transactions)
Problem Statement
You are given an array prices[] where prices[i] represents the stock price on day i.
You can perform multiple buy and sell transactions with the following rules:
- You must sell before buying again
- You can hold only one stock at a time
- You may buy and sell on the same day only once
Find the maximum profit achievable.
Example 1
Input
prices = [7, 1, 5, 3, 6, 4]
Output
7
Explanation
- Buy at 1 → Sell at 5 (Profit = 4)
- Buy at 3 → Sell at 6 (Profit = 3)
- Total Profit = 7
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Peak–Valley Greedy | O(n) | O(1) |
| Approach 3 | Sum of Positive Differences | O(n) | O(1) |
Approach 1: Brute Force
Idea
Check all possible buy–sell pairs and accumulate profit whenever selling price is higher than buying price.
Algorithm
- Initialize profit = 0
- For each day i
- For each future day j > i
- If prices[j] > prices[i], add profit and move i forward
- Continue until array ends
Implementation
C
#include
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6, profit = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (prices[j] > prices[i]) {
profit += prices[j] - prices[i];
i = j - 1;
break;
}
}
}
printf("Maximum Profit: %d", profit);
return 0;
}
C++
#include
using namespace std;
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6, profit = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (prices[j] > prices[i]) {
profit += prices[j] - prices[i];
i = j - 1;
break;
}
}
}
cout << "Maximum Profit: " << profit;
return 0;
}
Java
public class StockBuySell {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int profit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[j] > prices[i]) {
profit += prices[j] - prices[i];
i = j - 1;
break;
}
}
}
System.out.println("Maximum Profit: " + profit);
}
}
Python
prices = [7, 1, 5, 3, 6, 4]
profit = 0
i = 0
while i < len(prices) - 1:
j = i + 1
while j < len(prices):
if prices[j] > prices[i]:
profit += prices[j] - prices[i]
i = j - 1
break
j += 1
i += 1
print("Maximum Profit:", profit)
JavaScript
let prices = [7, 1, 5, 3, 6, 4];
let profit = 0;
for (let i = 0; i < prices.length - 1; i++) {
for (let j = i + 1; j < prices.length; j++) {
if (prices[j] > prices[i]) {
profit += prices[j] - prices[i];
i = j - 1;
break;
}
}
}
console.log("Maximum Profit:", profit);
Approach 2: Greedy Peak–Valley
Idea
- Buy at local minima
- Sell at local maxima
- Add each transaction’s profit
Algorithm
- Traverse prices
- Find valley (buy)
- Find peak (sell)
- Add sell - buy to profit
- Repeat
Implementation
C
#include
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6, i = 0, profit = 0;
while (i < n - 1) {
while (i < n - 1 && prices[i] >= prices[i + 1])
i++;
int buy = prices[i];
while (i < n - 1 && prices[i] <= prices[i + 1])
i++;
int sell = prices[i];
profit += sell - buy;
}
printf("Maximum Profit: %d", profit);
return 0;
}
C++
#include
using namespace std;
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6, i = 0, profit = 0;
while (i < n - 1) {
while (i < n - 1 && prices[i] >= prices[i + 1])
i++;
int buy = prices[i];
while (i < n - 1 && prices[i] <= prices[i + 1])
i++;
int sell = prices[i];
profit += sell - buy;
}
cout << "Maximum Profit: " << profit;
return 0;
}
Java
public class StockBuySell {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int i = 0, profit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
int buy = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
int sell = prices[i];
profit += sell - buy;
}
System.out.println("Maximum Profit: " + profit);
}
}
Python
prices = [7, 1, 5, 3, 6, 4]
i = 0
profit = 0
while i < len(prices) - 1:
while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
i += 1
buy = prices[i]
while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
i += 1
sell = prices[i]
profit += sell - buy
print("Maximum Profit:", profit)
JavaScript
let prices = [7, 1, 5, 3, 6, 4];
let i = 0, profit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
let buy = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
let sell = prices[i];
profit += sell - buy;
}
console.log("Maximum Profit:", profit);
Approach 3: Sum of Positive Differences (Best & Most Used)
Idea
Add profit whenever today’s price is greater than yesterday’s price.
Algorithm
- Initialize profit = 0
- Traverse from index 1
- If prices[i] > prices[i-1], add difference
- Return profit
Implementation
C
#include
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6, profit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
}
printf("Maximum Profit: %d", profit);
return 0;
}
C++
#include
using namespace std;
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int profit = 0;
for (int i = 1; i < 6; i++) {
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
}
cout << "Maximum Profit: " << profit;
return 0;
}
Java
public class StockBuySell {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
}
System.out.println("Maximum Profit: " + profit);
}
}
Python
prices = [7, 1, 5, 3, 6, 4]
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
print("Maximum Profit:", profit)
JavaScript
let prices = [7, 1, 5, 3, 6, 4];
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
console.log("Maximum Profit:", profit);
Final Summary
- Brute Force → learning purpose only
- Peak–Valley → conceptually clear
- Positive Difference Greedy → best, simplest, interview-preferred
Next problem in the series-
Sort an Array of 0s, 1s, and 2s
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
