Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Solution

Use a sliding window moving from left to right.

In the event that a value on the right is larger than the left, compute the profit and compare to current max profit. If it's larger reassign the max profit to the current max profit

If the left value of the window is larger than the right, update left to the current value of right. This has the effect of "closing" the window and starting over from the current value of right.

In this way we guarantee we always make a profit.

Initialize variables

Declare the variables we need to create our window. Also declare profit defaulted to 0 and return it at the end of the function.

1//
2 
3var maxProfit = function (prices) {
4  var l = 0
5  var r = 1
6  var profit = 0
7 
8  return profit
9}

1// Typescript requires type annotation on function parameters.
2 
3function maxProfit(prices: number[]): number {
4  var l = 0
5  var r = 1
6  var profit = 0
7 
8  return profit
9}

1# Python isn't a curly brace language.
2# It also has multi variable assignment.
3 
4class Solution:
5  def maxProfit(self, prices: List[int]) -> int:
6    profit, l, r = 0, 0, 1
7 
8    return profit

1// Dart requires semicolons at the end of line and type annotation for function
2// parameters.
3 
4// For variable declarations dart can infer type
5 
6class Solution {
7  int maxProfit(List<int> prices) {
8    var l = 0;
9    var r = 1;
10    var profit = 0;
11 
12    return profit;
13  }
14}

1// Java requires semicolons at the end of line and type annotation for function
2// parameters.
3 
4// There isn't inferred type in Java, we must explicitly type variables.
5 
6class Solution {
7  public int maxProfit(int[] prices) {
8    int l = 0;
9    int r = 1;
10    int profit = 0;
11 
12    return profit;
13  }
14}

1// Go has multi variable assignment and inferred type using the ':='
2 
3func maxProfit(prices []int) int {
4  profit, l, r := 0, 0, 1
5 
6  return profit
7}

Loop prices from left to right

Loop prices using our right pointer, r. On each iteration we increase r, growing our "window" into the input array.

1//
2 
3var maxProfit = function (prices) {
4  var l = 0
5  var r = 1
6  var profit = 0
7  while (r < prices.length) {
8    r += 1
9  }
10  return profit
11}

1//
2 
3function maxProfit(prices: number[]): number {
4  var l = 0
5  var r = 1
6  var profit = 0
7  while (r < prices.length) {
8    r += 1
9  }
10  return profit
11}

1# To find the length of a list in Python we use len()
2 
3class Solution:
4  def maxProfit(self, prices: List[int]) -> int:
5    profit, l, r = 0, 0, 1
6    while r < len(prices):
7      r += 1
8    return profit

1//
2class Solution {
3  int maxProfit(List<int> prices) {
4    var l = 0;
5    var r = 1;
6    var profit = 0;
7    while (r < prices.length) {
8      r += 1;
9    }
10    return profit;
11  }
12}

1//
2 
3class Solution {
4  public int maxProfit(int[] prices) {
5    int l = 0;
6    int r = 1;
7    int profit = 0;
8    while (r < prices.length) {
9      r += 1;
10    }
11    return profit;
12  }
13}

1// Go has no 'while' loop. To mimic a while loop use a for loop
2// with an explicitly declared iterator r, incrementing in the loop's body.
3 
4func maxProfit(prices []int) int {
5  profit, l, r := 0, 0, 1
6 
7  for r < len(prices) {
8    r += 1
9  }
10  return profit
11}

Check difference of future price and current price

Use the right pointer, r, to grab that future price and compare it using the left pointer, l, to the previous price.

Compare the current difference to previous differences. The difference is our profit.

On each iteration we use a built in Math.max function(or custom one) to reassign profit.

1// Math.max is built into javascript and can be used to find
2// the largest value between multiple values.
3 
4var maxProfit = function (prices) {
5  var l = 0
6  var r = 1
7  var profit = 0
8  while (r < prices.length) {
9    if (prices[r] > prices[l]) {
10      var cur = prices[r] - prices[l]
11      profit = Math.max(cur, profit)
12    } else {
13      l = r
14    }
15    r += 1
16  }
17  return profit
18}

1// Typescript also has a Math.max builtin function.
2 
3function maxProfit(prices: number[]): number {
4  var l = 0
5  var r = 1
6  var profit = 0
7  while (r < prices.length) {
8    if (prices[r] > prices[l]) {
9      var cur = prices[r] - prices[l]
10      profit = Math.max(cur, profit)
11    } else {
12      l = r
13    }
14    r += 1
15  }
16  return profit
17}

1# Python has max().
2 
3class Solution:
4  def maxProfit(self, prices: List[int]) -> int:
5    profit, l, r = 0, 0, 1
6    while r < len(prices):
7      if prices[r] > prices[l]:
8        cur = prices[r] - prices[l]
9        profit = max(profit, cur)
10      else:
11        l = r
12      r += 1
13    return profit

1// Dart has max() as well.
2 
3class Solution {
4  int maxProfit(List<int> prices) {
5    var l = 0;
6    var r = 1;
7    var profit = 0;
8    while (r < prices.length) {
9      if (prices[l] < prices[r]) {
10        var cur = prices[r] - prices[l];
11        profit = max(cur, profit);
12      } else {
13        l = r;
14      }
15      r += 1;
16    }
17    return profit;
18  }
19}

1// Java also has a builtin Math.max
2 
3class Solution {
4  public int maxProfit(int[] prices) {
5    int l = 0;
6    int r = 1;
7    int profit = 0;
8    while (r < prices.length) {
9      if (prices[r] > prices[l]) {
10        int cur = prices[r] - prices[l];
11        profit = Math.max(cur, profit);
12      } else {
13        l = r;
14      }
15      r += 1;
16    }
17    return profit;
18  }
19}

1// Go doesn't have a built in function for identifying max of two ints
2// So we have to implement it ourselves
3 
4func Max(x, y int) int {
5  if x < y {
6    return y
7  }
8  return x
9}
10 
11func maxProfit(prices []int) int {
12  profit, l, r := 0, 0, 1
13 
14  for r < len(prices) {
15    if prices[l] < prices[r] {
16      cur := prices[r] - prices[l]
17      profit = Max(profit, cur)
18    } else {
19      l = r
20    }
21    r += 1
22  }
23  return profit
24}

Questions? Concerns?

Please comment a better solution if you have one.