101 Logo
onenoughtone

Code Implementation

Stock Profit Maximizer Implementation

Below is the implementation of the stock profit maximizer:

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
/**
 * Find the maximum profit from a single buy and sell transaction.
 * One-Pass approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfit(prices) {
  if (prices.length < 2) {
    return 0;
  }
 
  let minPrice = Infinity;
  let maxProfit = 0;
 
  for (let i = 0; i < prices.length; i++) {
    // Update the minimum price seen so far
    minPrice = Math.min(minPrice, prices[i]);
 
    // Calculate potential profit if we sell at current price
    const currentProfit = prices[i] - minPrice;
 
    // Update maximum profit if current profit is higher
    maxProfit = Math.max(maxProfit, currentProfit);
  }
 
  return maxProfit;
}
 
/**
 * Find the maximum profit from a single buy and sell transaction.
 * Kadane's Algorithm approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitKadane(prices) {
  if (prices.length < 2) {
    return 0;
  }
 
  let maxCurr = 0;
  let maxSoFar = 0;
 
  for (let i = 1; i < prices.length; i++) {
    // Calculate price difference
    const diff = prices[i] - prices[i - 1];
 
    // Update maximum profit ending at current position
    maxCurr = Math.max(0, maxCurr + diff);
 
    // Update maximum profit found so far
    maxSoFar = Math.max(maxSoFar, maxCurr);
  }
 
  return maxSoFar;
}
 
/**
 * Find the maximum profit from a single buy and sell transaction.
 * Brute Force approach.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitBruteForce(prices) {
  if (prices.length < 2) {
    return 0;
  }
 
  let maxProfit = 0;
 
  // Consider all possible buy and sell days
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      // Calculate profit for this buy-sell pair
      const profit = prices[j] - prices[i];
 
      // Update maximum profit if current profit is higher
      maxProfit = Math.max(maxProfit, profit);
    }
  }
 
  return maxProfit;
}
 
// Test cases
console.log(maxProfit([7, 1, 5, 3, 6, 4]));  // 5
console.log(maxProfit([7, 6, 4, 3, 1]));  // 0
 
console.log(maxProfitKadane([7, 1, 5, 3, 6, 4]));  // 5
console.log(maxProfitKadane([7, 6, 4, 3, 1]));  // 0
 
console.log(maxProfitBruteForce([7, 1, 5, 3, 6, 4]));  // 5
console.log(maxProfitBruteForce([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 a single buy and sell transaction, where we must buy before selling.
  2. Initialize Variables: Initialize variables to track the minimum price seen so far and the maximum profit.
  3. Iterate Through Prices: Iterate through the array of prices, updating the minimum price and calculating the potential profit at each step.
  4. Update Maximum Profit: Update the maximum profit if the current potential profit is higher.
  5. Handle Edge Cases: Handle edge cases such as arrays with fewer than 2 elements, where no profit is possible.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone