101 Logo
onenoughtone

Code Implementation

Stock Trader with Two Transactions Implementation

Below is the implementation of the stock trader with two transactions:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * Find the maximum profit with at most two transactions.
 * Dynamic Programming with Four States approach.
 * 
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfit(prices) {
  if (prices.length <= 1) {
    return 0;
  }
  
  let buy1 = -prices[0];  // Maximum profit after buying the first stock
  let sell1 = 0;  // Maximum profit after selling the first stock
  let buy2 = -prices[0];  // Maximum profit after buying the second stock
  let sell2 = 0;  // Maximum profit after selling the second stock
  
  for (let i = 1; i < prices.length; i++) {
    // Update buy1: either keep the previous state or buy the first stock
    buy1 = Math.max(buy1, -prices[i]);
    
    // Update sell1: either keep the previous state or sell the first stock
    sell1 = Math.max(sell1, buy1 + prices[i]);
    
    // Update buy2: either keep the previous state or buy the second stock
    buy2 = Math.max(buy2, sell1 - prices[i]);
    
    // Update sell2: either keep the previous state or sell the second stock
    sell2 = Math.max(sell2, buy2 + prices[i]);
  }
  
  return sell2;
}
 
/**
 * Find the maximum profit with at most two transactions.
 * Dynamic Programming with Arrays approach.
 * 
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitWithArrays(prices) {
  if (prices.length <= 1) {
    return 0;
  }
  
  const n = prices.length;
  const buy1 = new Array(n).fill(0);
  const sell1 = new Array(n).fill(0);
  const buy2 = new Array(n).fill(0);
  const sell2 = new Array(n).fill(0);
  
  buy1[0] = -prices[0];
  buy2[0] = -prices[0];
  
  for (let i = 1; i < n; i++) {
    // Update buy1: either keep the previous state or buy the first stock
    buy1[i] = Math.max(buy1[i - 1], -prices[i]);
    
    // Update sell1: either keep the previous state or sell the first stock
    sell1[i] = Math.max(sell1[i - 1], buy1[i - 1] + prices[i]);
    
    // Update buy2: either keep the previous state or buy the second stock
    buy2[i] = Math.max(buy2[i - 1], sell1[i - 1] - prices[i]);
    
    // Update sell2: either keep the previous state or sell the second stock
    sell2[i] = Math.max(sell2[i - 1], buy2[i - 1] + prices[i]);
  }
  
  return sell2[n - 1];
}
 
/**
 * Find the maximum profit with at most two transactions.
 * Split and Conquer approach.
 * 
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitSplitAndConquer(prices) {
  if (prices.length <= 1) {
    return 0;
  }
  
  const n = prices.length;
  const leftProfit = new Array(n).fill(0);
  const rightProfit = new Array(n).fill(0);
  
  // Calculate leftProfit: maximum profit from a single transaction on days 0 to i
  let minPrice = prices[0];
  for (let i = 1; i < n; i++) {
    minPrice = Math.min(minPrice, prices[i]);
    leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice);
  }
  
  // Calculate rightProfit: maximum profit from a single transaction on days i to n-1
  let maxPrice = prices[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    maxPrice = Math.max(maxPrice, prices[i]);
    rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]);
  }
  
  // Find the maximum combined profit
  let maxProfit = 0;
  for (let i = 0; i < n; i++) {
    maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]);
  }
  
  return maxProfit;
}
 
// Test cases
console.log(maxProfit([3, 3, 5, 0, 0, 3, 1, 4]));  // 6
console.log(maxProfit([1, 2, 3, 4, 5]));  // 4
console.log(maxProfit([7, 6, 4, 3, 1]));  // 0
 
console.log(maxProfitWithArrays([3, 3, 5, 0, 0, 3, 1, 4]));  // 6
console.log(maxProfitWithArrays([1, 2, 3, 4, 5]));  // 4
console.log(maxProfitWithArrays([7, 6, 4, 3, 1]));  // 0
 
console.log(maxProfitSplitAndConquer([3, 3, 5, 0, 0, 3, 1, 4]));  // 6
console.log(maxProfitSplitAndConquer([1, 2, 3, 4, 5]));  // 4
console.log(maxProfitSplitAndConquer([7, 6, 4, 3, 1]));  // 0

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: First, understand that we need to find the maximum profit from at most two transactions, where we must sell before buying again.
  2. Define State Variables: Define state variables to track the maximum profit after different states of transactions: buying the first stock, selling the first stock, buying the second stock, and selling the second stock.
  3. Iterate Through Prices: Iterate through the array of prices, updating the state variables based on the possible actions: buy, sell, or do nothing.
  4. Consider Alternative Approaches: Consider alternative approaches such as using arrays to track the maximum profit at each day, or splitting the problem into two parts.
  5. Return Maximum Profit: Return the maximum profit, which will be the maximum profit after selling the second stock.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone