101 Logo
onenoughtone

Code Implementation

Stock Trader with K Transactions Implementation

Below is the implementation of the stock trader with k 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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/**
 * Find the maximum profit with at most k transactions.
 * Dynamic Programming with 2K States approach.
 * 
 * @param {number} k - Maximum number of transactions
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfit(k, prices) {
  const n = prices.length;
  
  // Edge cases
  if (k === 0 || n === 0) {
    return 0;
  }
  
  // If k is large, use the greedy approach
  if (k >= Math.floor(n / 2)) {
    let maxProfit = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
      }
    }
    return maxProfit;
  }
  
  // Initialize arrays
  const buy = new Array(k + 1).fill(-Infinity);
  const sell = new Array(k + 1).fill(0);
  
  // Set initial values
  for (let j = 1; j <= k; j++) {
    buy[j] = -prices[0];
  }
  
  // Dynamic programming
  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      // Update buy: either keep the previous state or buy the j-th stock
      buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
      
      // Update sell: either keep the previous state or sell the j-th stock
      sell[j] = Math.max(sell[j], buy[j] + prices[i]);
    }
  }
  
  return sell[k];
}
 
/**
 * Find the maximum profit with at most k transactions.
 * Dynamic Programming with 2D Arrays approach.
 * 
 * @param {number} k - Maximum number of transactions
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitWith2DArrays(k, prices) {
  const n = prices.length;
  
  // Edge cases
  if (k === 0 || n === 0) {
    return 0;
  }
  
  // If k is large, use the greedy approach
  if (k >= Math.floor(n / 2)) {
    let maxProfit = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
      }
    }
    return maxProfit;
  }
  
  // Initialize 2D arrays
  const buy = Array(n).fill().map(() => Array(k + 1).fill(-Infinity));
  const sell = Array(n).fill().map(() => Array(k + 1).fill(0));
  
  // Set initial values
  for (let j = 1; j <= k; j++) {
    buy[0][j] = -prices[0];
  }
  
  // Dynamic programming
  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      // Update buy: either keep the previous state or buy the j-th stock
      buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j - 1] - prices[i]);
      
      // Update sell: either keep the previous state or sell the j-th stock
      sell[i][j] = Math.max(sell[i - 1][j], buy[i][j] + prices[i]);
    }
  }
  
  return sell[n - 1][k];
}
 
/**
 * Find the maximum profit with at most k transactions.
 * Optimized Dynamic Programming approach.
 * 
 * @param {number} k - Maximum number of transactions
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitOptimized(k, prices) {
  const n = prices.length;
  
  // Edge cases
  if (k === 0 || n === 0) {
    return 0;
  }
  
  // If k is large, use the greedy approach
  if (k >= Math.floor(n / 2)) {
    let maxProfit = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
      }
    }
    return maxProfit;
  }
  
  // Initialize arrays
  const buy = new Array(k + 1).fill(-Infinity);
  const sell = new Array(k + 1).fill(0);
  
  // Set initial values
  for (let j = 1; j <= k; j++) {
    buy[j] = -prices[0];
  }
  
  // Dynamic programming
  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      // We need to use temporary variables to avoid using updated values in the same iteration
      const prevBuy = buy[j];
      const prevSell = sell[j - 1];
      
      // Update buy: either keep the previous state or buy the j-th stock
      buy[j] = Math.max(prevBuy, prevSell - prices[i]);
      
      // Update sell: either keep the previous state or sell the j-th stock
      sell[j] = Math.max(sell[j], prevBuy + prices[i]);
    }
  }
  
  return sell[k];
}
 
// Test cases
console.log(maxProfit(2, [2, 4, 1]));  // 2
console.log(maxProfit(2, [3, 2, 6, 5, 0, 3]));  // 7
 
console.log(maxProfitWith2DArrays(2, [2, 4, 1]));  // 2
console.log(maxProfitWith2DArrays(2, [3, 2, 6, 5, 0, 3]));  // 7
 
console.log(maxProfitOptimized(2, [2, 4, 1]));  // 2
console.log(maxProfitOptimized(2, [3, 2, 6, 5, 0, 3]));  // 7

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 k transactions, where we must sell before buying again.
  2. Handle Edge Cases: Handle edge cases such as k = 0, empty prices array, and k >= n/2 (where we can make as many transactions as we want).
  3. Define State Variables: Define state variables to track the maximum profit after different states of transactions: buying and selling stocks for each transaction.
  4. Iterate Through Prices: Iterate through the array of prices, updating the state variables based on the possible actions: buy, sell, or do nothing.
  5. Return Maximum Profit: Return the maximum profit, which will be the maximum profit after selling the k-th stock.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone